@article{Charikar-Khuller-Raghavachari/02,
AUTHOR = {Charikar, Moses and Khuller, Samir and Raghavachari, Balaji},
TITLE = {Algorithms for capacitated vehicle routing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {665-682},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {vehicle routing, traveling salesman problem, approximation algorithms, graphs},
URL = {http://dx.doi.org/10.1137/S0097539701392056},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Martnez-Roura/02,
AUTHOR = {Mart{\'{\i}}nez, Conrado and Roura, Salvador},
TITLE = {Optimal sampling strategies in Quicksort and Quickselect},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {683-705},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quicksort, quickselect, sorting, selection, sampling, median-of-$(2k+1)$, analysis of algorithms, divide-and-conquer},
URL = {http://dx.doi.org/10.1137/S0097539700382108},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gavoille-Peleg/02,
AUTHOR = {Gavoille, Cyril and Peleg, David},
TITLE = {The compactness of interval routing for almost all graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {706-721},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {interval routing, compact routing, random graphs},
URL = {http://dx.doi.org/10.1137/S0097539799351717},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ben-Amram-Galil/02a,
AUTHOR = {Ben-Amram, Amir M. and Galil, Zvi},
TITLE = {Topological lower bounds on algebraic random access machines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {722-761},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algebraic computation trees, element distinctness, knapsack, component counting arguments},
URL = {http://dx.doi.org/10.1137/S0097539797329397},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Munro-Raman/02,
AUTHOR = {Munro, J. Ian and Raman, Venkatesh},
TITLE = {Succinct representation of balanced parentheses and static trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {762-776},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {abstract data type, succinct representation, binary trees, balanced parenthesis, rooted ordered trees, planar graphs},
URL = {http://dx.doi.org/10.1137/S0097539799364092},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Therien-Wilke/02a,
AUTHOR = {Th{\'{e}}rien, Denis and Wilke, Thomas},
TITLE = {Temporal logic and semidirect products: An effective characterization of the until hierarchy},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {777-798},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {linear temporal logic, until hierarchy, substitution, finite semigroups, pseudovarieties of semigroups, aperiodic semigroups, semidirect products},
URL = {http://dx.doi.org/10.1137/S0097539797322772},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Moore-Nilsson/02,
AUTHOR = {Moore, Cristopher and Nilsson, Martin},
TITLE = {Parallel quantum computation and quantum codes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {799-815},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quantum circuits, parallel computation, quantum complexity classes, quantum error-correcting codes, group theory},
URL = {http://dx.doi.org/10.1137/S0097539799355053},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gafni-Mitzenmacher/02,
AUTHOR = {Gafni, Eli and Mitzenmacher, Michael},
TITLE = {Analysis of timing-based mutual exclusion with random times},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {816-837},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {mutual exclusion, timed mutual exclusion, markov chains, locks},
URL = {http://dx.doi.org/10.1137/S0097539799364912},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Halpern-Moses-Waarts/02,
AUTHOR = {Halpern, Joseph Y. and Moses, Yoram and Waarts, Orli},
TITLE = {A characterization of eventual Byzantine agreement},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {838-865},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {fault-tolerance, eventual byzantine agreement, common knowledge, continual common knowledge, optimal protocol},
URL = {http://dx.doi.org/10.1137/S0097539798340217},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chakrabarti-Khot-Shi/02,
AUTHOR = {Chakrabarti, Amit and Khot, Subhash and Shi, Yaoyun},
TITLE = {Evasiveness of subgraph containment and related properties},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {866-875},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {decision tree complexity, monotone graph properties, evasiveness, topological method, graph property testing},
URL = {http://dx.doi.org/10.1137/S0097539700382005},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Buhrman-Longpre/02,
AUTHOR = {Buhrman, Harry and Longpr{\'{e}}, Luc},
TITLE = {Compressibility and resource bounded measure},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {876-886},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {resource bounded measure, kolmogorov complexity, compressibility},
URL = {http://dx.doi.org/10.1137/S0097539797317123},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Buhrman-Fortnow-Laplante/02,
AUTHOR = {Buhrman, Harry and Fortnow, Lance and Laplante, Sophie},
TITLE = {Resource-bounded Kolmogorov complexity revisited},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {887-905},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computational complexity, kolmogorov complexity, cd complexity},
URL = {http://dx.doi.org/10.1137/S009753979834388X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pavan-Selman/02a,
AUTHOR = {Pavan, A. and Selman, Alan L.},
TITLE = {Separation of $NP$-completeness notions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {906-918},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {turing completeness, truth-table completeness, many-one completeness, $p$-selectivity, $p$-genericity},
URL = {http://dx.doi.org/10.1137/S0097539701387039},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kolliopoulos-Stein/02,
AUTHOR = {Kolliopoulos, Stavros G. and Stein, Clifford},
TITLE = {Approximation algorithms for single-source unsplittable flow},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {919-946},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, network algorithms, routing, network flow, unsplittable flow, disjoint paths, parallel machine scheduling},
URL = {http://dx.doi.org/10.1137/S0097539799355314},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boreale-de_Nicola-Pugliese/02a,
AUTHOR = {Boreale, Michele and de Nicola, Rocco and Pugliese, Rosario},
TITLE = {Proof techniques for cryptographic processes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {947-986},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {process calculi, reasoning about security, semantics, formal methods},
URL = {http://dx.doi.org/10.1137/S0097539700377864},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rieger/02,
AUTHOR = {Rieger, J.H.},
TITLE = {Erratum to ''Proximity in arrangements of algebraic sets''},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {987-987},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
URL = {http://dx.doi.org/10.1137/S0097539700380201},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {Originally in SIAM J. Comp., Vol. 29, 1999, No. 2, 433-458},
}
@article{Frieze/02a,
AUTHOR = {Frieze, Alan},
TITLE = {Erratum to ''Edge-disjoint paths in expander graphs''},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {3},
PAGES = {988-988},
YEAR = {2001-2002},
EDITOR = {Yannakakis, M.},
URL = {http://dx.doi.org/10.1137/S0097539701395097},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {Originally in SIAM J. Comp., Vol. 30, 2001, No. 6, 1790-1801},
}
@article{Moses-Rajsbaum/02,
AUTHOR = {Moses, Yoram and Rajsbaum, Sergio},
TITLE = {A layered analysis of consensus},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {989-1021},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {distributed systems, shaved-memory systems, topology, consensus, impossibility results, lower bounds},
URL = {http://dx.doi.org/10.1137/S0097539799364006},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Laber-Milidiu-Pessoa/02,
AUTHOR = {Laber, Eduardo S. and Milidi{\'{u}}, Ruy L. and Pessoa, Artur A.},
TITLE = {On binary searching with nonuniform costs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1022-1047},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {search trees, approximation algorithms, scaling},
URL = {http://dx.doi.org/10.1137/S0097539700381991},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Beame-Karp-Pitassi-Saks/02,
AUTHOR = {Beame, Paul and Karp, Richard and Pitassi, Toniann and Saks, Michael},
TITLE = {The efficiency of resolution and Davis-Putnam procedures},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1048-1075},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {proof complexity, resolution, Davis-Putnam procedure, satisfiability, random formulas, search algorithms, lower bounds},
URL = {http://dx.doi.org/10.1137/S0097539700369156},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Durr-Santha/02,
AUTHOR = {D{\"{u}}rr, Christoph and Santha, Miklos},
TITLE = {A decision procedure for unitary linear quantum cellular automata},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1076-1089},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quantum computation, reversible cellular automata},
URL = {http://dx.doi.org/10.1137/S0097539797327702},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feige-Krauthgamer/02,
AUTHOR = {Feige, Uriel and Krauthgamer, Robert},
TITLE = {A polylogarithmic approximation of the minimum bisection},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1090-1118},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, graph partitioning, graph separators, dynamic programming, divide and conquer},
URL = {http://dx.doi.org/10.1137/S0097539701387660},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Merkle/02a,
AUTHOR = {Merkle, Wolfgang},
TITLE = {Lattice embeddings for abstract bounded reducibilities},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1119-1155},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {resource-bounded reducibilities, embeddings of partial orderings, embeddings of distributive lattices, abstract reducibilities, axiomatization of reducibilities},
URL = {http://dx.doi.org/10.1137/S0097539701385958},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Geser/02,
AUTHOR = {Geser, Alfons},
TITLE = {Decidability of termination of grid string rewriting rules},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1156-1168},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {semi-thue system, string rewriting system, one-rule, termination, grid rule, total division order},
URL = {http://dx.doi.org/10.1137/S009753979833297X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Downey-Hirschfeldt-Nies/02,
AUTHOR = {Downey, Rod G. and Hirschfeldt, Denis R. and Nies, Andr{\'{e}}},
TITLE = {Randomness, computability, and density},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1169-1183},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {randomness, computably enumerable reals, algorithmic information theory, kolmogorov complexity, solovay reducibility},
URL = {http://dx.doi.org/10.1137/S0097539700376937},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alekhnovich-Ben-Sasson-Razborov-Wigderson/02,
AUTHOR = {Alekhnovich, Michael and Ben-Sasson, Eli and Razborov, Alexander A. and Wigderson, Avi},
TITLE = {Space complexity in propositional calculus},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1184-1211},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {proof complexity, resolution, frege, polynomial calculus},
URL = {http://dx.doi.org/10.1137/S0097539700366735},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Theobald/02,
AUTHOR = {Theobald, Thorsten},
TITLE = {An enumerative geometry framework for algorithmic line problems in $R^3$},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1212-1228},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {tangents, balls, transversals, lines, enumerative geometry, real solutions, computational geometry},
URL = {http://dx.doi.org/10.1137/S009753970038050X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Valiant/02,
AUTHOR = {Valiant, Leslie G.},
TITLE = {Quantum circuits that can be simulated classically in polynomial time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1229-1254},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quantum computation, turing hypothesis, matchgates, polynomial time simulation},
URL = {http://dx.doi.org/10.1137/S0097539700377025},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-He-Huang/02,
AUTHOR = {Chen, Zhi-Zhong and He, Xin and Huang, Chun-Hsi},
TITLE = {Finding double Euler trails of planar graphs in linear time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1255-1285},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {planar graph, dual graph, euler trail},
URL = {http://dx.doi.org/10.1137/S0097539799354321},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Attiya-Rajsbaum/02,
AUTHOR = {Attiya, Hagit and Rajsbaum, Sergio},
TITLE = {The combinatorial structure of wait-free solvable tasks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {4},
PAGES = {1286-1313},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {distributed systems, shared memory systems, atomic read/write registers, combinatorial topology, wait-free solvable tasks, consensus, set consensus, renaming},
URL = {http://dx.doi.org/10.1137/S0097539797330689},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chvatal-Fonlupt-Sun-Zemirline/02,
AUTHOR = {Chv{\'{a}}tal, V. and Fonlupt, J. and Sun, L. and Zemirline, A.},
TITLE = {Recognizing dart-free perfect graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1315-1338},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {perfect graphs},
URL = {http://dx.doi.org/10.1137/S0097539799354771},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Zhou-Suri/02,
AUTHOR = {Zhou, Yunhong and Suri, Subhash},
TITLE = {Algorithms for a minimum volume enclosing simplex in three dimensions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1339-1357},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {shape approximation, bounding volumes, centroid},
URL = {http://dx.doi.org/10.1137/S0097539799363992},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Servedio/02,
AUTHOR = {Servedio, Rocco A.},
TITLE = {Perceptron, Winnow, and PAC learning},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1358-1369},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {linear threshold function, pac learning, perceptron, winnow},
URL = {http://dx.doi.org/10.1137/S0097539798340928},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Awerbuch-Azar-Leonardi-Regev/02,
AUTHOR = {Awerbuch, Baruch and Azar, Yossi and Leonardi, Stefano and Regev, Oded},
TITLE = {Minimizing the flow time without migration},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1370-1382},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {scheduling, flow time, migration, approximation, online},
URL = {http://dx.doi.org/10.1137/S009753970037446X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Naor-Reingold-Rosen/02,
AUTHOR = {Naor, Moni and Reingold, Omer and Rosen, Alon},
TITLE = {Pseudorandom functions and factoring},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1383-1404},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {cryptography, pseudorandomness, pseudorandom functions, computational number theory, integer factorization},
URL = {http://dx.doi.org/10.1137/S0097539701389257},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hiptmair-Ostrowski/02,
AUTHOR = {Hiptmair, R. and Ostrowski, J.},
TITLE = {Generators of $H_1(\Gamma_h, Z)$ for triangulated surfaces: Construction and classification},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1405-1423},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {cellular homology, nonbounding cycles, linking numbers, surface stream functions, computational electromagnetism},
URL = {http://dx.doi.org/10.1137/S0097539701386526},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gal-Rosen/02,
AUTHOR = {G{\'{a}}l, Anna and Ros{\'{e}}n, Adi},
TITLE = {A theorem on sensitivity and applications in private computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1424-1437},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {sensitivity, private computation, randomness, lower bounds},
URL = {http://dx.doi.org/10.1137/S0097539701385296},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Malvestuto-Mezzini/02,
AUTHOR = {Malvestuto, F.M. and Mezzini, M.},
TITLE = {A linear algorithm for finding the invariant edges of an edge-weighted graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1438-1455},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {linear algebra, graph algorithms, matroid theory},
URL = {http://dx.doi.org/10.1137/S0097539700376068},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Brodsky-Pippenger/02,
AUTHOR = {Brodsky, Alex and Pippenger, Nicholas},
TITLE = {Characterizations of 1-way quantum finite automata},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1456-1478},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quantum finite automata, quantum computation, automata theory},
URL = {http://dx.doi.org/10.1137/S0097539799353443},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gudmundsson-Levcopoulos-Narasimhan/02,
AUTHOR = {Gudmundsson, Joachim and Levcopoulos, Christos and Narasimhan, Giri},
TITLE = {Fast greedy algorithms for constructing sparse geometric spanners},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1479-1500},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computational geometry, sparse geometric spanners, cluster graph},
URL = {http://dx.doi.org/10.1137/S0097539700382947},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Klivans-van_Melkebeek/02,
AUTHOR = {Klivans, Adam R. and van Melkebeek, Dieter},
TITLE = {Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1501-1526},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {derandomization, pseudorandomness, graph isomorphism, interactive proofs, arthur-merlin games, hardness versus randomness, universal traversal sequences, unique satisfiability, learning theory, rigid matrices},
URL = {http://dx.doi.org/10.1137/S0097539700389652},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dyer-Frieze-Jerrum/02,
AUTHOR = {Dyer, Martin and Frieze, Alan and Jerrum, Mark},
TITLE = {On counting independent sets in sparse graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1527-1541},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
URL = {http://dx.doi.org/10.1137/S0097539701383844},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Spreen/02,
AUTHOR = {Spreen, Dieter},
TITLE = {Safe weak minimization revisited},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1542-1556},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {implicit computational complexity, safe (predicative) recursion, recursion on notation, minimization, nondeterministic polynomial time, multifunction, normal form theorem},
URL = {http://dx.doi.org/10.1137/S0097539701387854},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Newman/02,
AUTHOR = {Newman, Ilan},
TITLE = {Testing membership in languages that have small width branching programs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1557-1570},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {property testing, randomized algorithms, branching programs},
URL = {http://dx.doi.org/10.1137/S009753970038211X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mayer-Ostrovsky-Ofek-Yung/02,
AUTHOR = {Mayer, Alain and Ostrovsky, Rafail and Ofek, Yoram and Yung, Moti},
TITLE = {Self-stabilizing symmetry breaking in constant space},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1571-1595},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {self-stabilization, self-stabilizing protocols, distributed algorithms, token ring protocols, media access protocols},
URL = {http://dx.doi.org/10.1137/S0097539798285997},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feder-Motwani-Subi/02,
AUTHOR = {Feder, Tom{\'{a}}s and Motwani, Rajeev and Subi, Carlos},
TITLE = {Approximating the longest cycle problem in sparse graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1596-1607},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {long paths and cycles, hamiltonian graphs, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S0097539701395486},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Halperin/02,
AUTHOR = {Halperin, Eran},
TITLE = {Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1608-1623},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {vertex cover, semidefinite programming, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S0097539700381097},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boros-Elbassioni-Gurvich-Khachiyan-Makino/02,
AUTHOR = {Boros, E. and Elbassioni, K. and Gurvich, V. and Khachiyan, L. and Makino, K.},
TITLE = {Dual-bounded generating problems: All minimal integer solutions for a monotone system of linear inequalities},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {5},
PAGES = {1624-1643},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {integer programming, complexity of incremental algorithms, dualization, quasi-polynomial time, monotone discrete binary functions, monotone inequalities, regular discrete functions},
URL = {http://dx.doi.org/10.1137/S0097539701388768},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Russell-Saks-Zuckerman/02,
AUTHOR = {Russell, Alexander and Saks, Michael and Zuckerman, David},
TITLE = {Lower bounds for leader election and collective coin-flipping in the perfect information model},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1645-1662},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {perfect information model, collective coin-flipping, leader election},
URL = {http://dx.doi.org/10.1137/S0097539700376007},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Guruswami-Hastad-Sudan/02,
AUTHOR = {Guruswami, Venkatesan and H{\aa}stad, Johan and Sudan, Madhu},
TITLE = {Hardness of approximate hypergraph coloring},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1663-1686},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {graph coloring, hypergraph coloring, hardness of approximations, pcp, covering pcp, set splitting},
URL = {http://dx.doi.org/10.1137/S0097539700377165},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hwang-Neininger/02,
AUTHOR = {Hwang, Hsien-Kuei and Neininger, Ralph},
TITLE = {Phase change of limit laws in the Quicksort recurrence under varying toll functions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1687-1722},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quicksort, binary search trees, analysis of algorithms, limit distribution, method of moments, contraction method},
URL = {http://dx.doi.org/10.1137/S009753970138390X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Buhrman-Miltersen-Radhakrishnan-Venkatesh/02,
AUTHOR = {Buhrman, H. and Miltersen, P.B. and Radhakrishnan, J. and Venkatesh, S.},
TITLE = {Are bitvectors optimal?},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1723-1744},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {data structures, set membership problem, bit probe model, set systems},
URL = {http://dx.doi.org/10.1137/S0097539702405292},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pach-Tardos/02b,
AUTHOR = {Pach, J{\'{a}}nos and Tardos, G{\'{a}}bor},
TITLE = {On the boundary complexity of the union of fat triangles},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1745-1760},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {holes, boundary complexity, fat objects},
URL = {http://dx.doi.org/10.1137/S0097539700382169},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cole-Hariharan/02,
AUTHOR = {Cole, Richard and Hariharan, Ramesh},
TITLE = {Approximate string matching: A simpler faster algorithm},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1761-1782},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algorithms, string matching, edit distance},
URL = {http://dx.doi.org/10.1137/S0097539700370527},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Konemann-Ravi/02,
AUTHOR = {K{\"{o}}nemann, J. and Ravi, R.},
TITLE = {A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1783-1793},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, network algorithms, bicriteria approximation, spanning trees, degree-bounded spanning trees, lagrangean relaxation},
URL = {http://dx.doi.org/10.1137/S009753970036917X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Datar-Gionis-Indyk-Motwani/02,
AUTHOR = {Datar, Mayur and Gionis, Aristides and Indyk, Piotr and Motwani, Rajeev},
TITLE = {Maintaining stream statistics over sliding windows},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1794-1813},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {statistics, data streams, sliding windows, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S0097539701398363},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwal-Biedl-Lazard-Robbins-Suri-Whitesides/02,
AUTHOR = {Agarwal, Pankaj K. and Biedl, Therese and Lazard, Sylvain and Robbins, Steve and Suri, Subhash and Whitesides, Sue},
TITLE = {Curvature-constrained shortest paths in a convex polygon},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1814-1851},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {nonholonomic motion planning, shortest paths, mobile robot, curvature constraint, bounded radius of curvature, dubins path, computational geometry},
URL = {http://dx.doi.org/10.1137/S0097539700374550},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Han-Shen/02,
AUTHOR = {Han, Yijie and Shen, Xiaojun},
TITLE = {Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1852-1878},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algorithms, analysis of algorithms, bucket sorting, conservative algorithms, design of algorithms, integer sorting, parallel algorithms},
URL = {http://dx.doi.org/10.1137/S0097539799352449},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pettie-Ramachandran/02a,
AUTHOR = {Pettie, Seth and Ramachandran, Vijaya},
TITLE = {A randomized time-work optimal parallel algorithm for finding a minimum spanning forest},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1879-1895},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {parallel algorithm, minimum spanning tree, optimal algorithm, erew pram},
URL = {http://dx.doi.org/10.1137/S0097539700371065},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kutz/02,
AUTHOR = {Kutz, Martin},
TITLE = {Lower bounds for Lucas chains},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1896-1908},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {lucas chain, addition chain, lucas function, lower bound, fibonacci number, golden ratio, smooth number},
URL = {http://dx.doi.org/10.1137/S0097539700379255},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bshouty-Mansour/02,
AUTHOR = {Bshouty, Nader H. and Mansour, Yishay},
TITLE = {Simple learning algorithms for decision trees and multivariate polynomials},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1909-1925},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {learning interpolation, multivariate polynomial, decision tree learning},
URL = {http://dx.doi.org/10.1137/S009753979732058X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lefmann-Schmitt/02,
AUTHOR = {Lefmann, Hanno and Schmitt, Niels},
TITLE = {A deterministic polynomial-time algorithm for Heilbronn's problem in three dimensions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1926-1947},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {Heilbronn's triangle problem, arrangements of simplices, independent sets in hypergraphs},
URL = {http://dx.doi.org/10.1137/S0097539701395115},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hemaspaandra-Wechsung/02,
AUTHOR = {Hemaspaandra, Edith and Wechsung, Gerd},
TITLE = {The minimization problem for Boolean formulas},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {6},
PAGES = {1948-1958},
YEAR = {2002},
EDITOR = {Yannakakis, M.},
KEYWORDS = {boolean formula minimization, parallel access, computational complexity, polynomial hierarchy, reductions},
URL = {http://dx.doi.org/10.1137/S0097539799362639},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}