@article{Ben-Sasson-Harsha-Raskhodnikova/05,
AUTHOR = {Ben-Sasson, Eli and Harsha, Prahladh and Raskhodnikova, Sofya},
TITLE = {Some 3CNF properties are hard to test},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {1-21},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {sublinear algorithms, lower bounds, property testing, cnf formulae, locally testable codes},
URL = {http://link.aip.org/link/?SMJ/35/1/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lindenbaum-Samet-Hjaltason/05,
AUTHOR = {Lindenbaum, Michael and Samet, Hanan and Hjaltason, Gisli R.},
TITLE = {A probabilistic analysis of trie-based sorting of large collections of line segments in spatial databases},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {22-58},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {large spatial databases, query evaluation, tries, sorting line segments, geometric probability, analysis of algorithms, spatial data structures, quadtrees, quadtries, cost model},
URL = {http://link.aip.org/link/?SMJ/35/22/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{van_Melkebeek-Santhanam/05,
AUTHOR = {van Melkebeek, Dieter and Santhanam, Rahul},
TITLE = {Holographic proofs and derandomization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {59-90},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {holographic proofs, derandomization, arthur-merlin games},
URL = {http://link.aip.org/link/?SMJ/35/59/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Czumaj-Ergun-Fortnow-Magen-Newman-Rubinfeld-Sohler/05,
AUTHOR = {Czumaj, Artur and Erg{\"u}n, Funda and Fortnow, Lance and Magen, Avner and Newman, Ilan and Rubinfeld, Ronitt and Sohler, Christian},
TITLE = {Approximating the weight of the Euclidean minimum spanning tree in sublinear time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {91-109},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {sublinear algorithms, minimum spanning tree},
URL = {http://link.aip.org/link/?SMJ/35/91/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jansen-Karpinski-Lingas-Seidel/05,
AUTHOR = {Jansen, Klaus and Karpinski, Marek and Lingas, Andrzej and Seidel, Eike},
TITLE = {Polynomial time approximation schemes for max-bisection on planar and geometric graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {110-119},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {combinatorial optimization, np-hardness, approximation algorithms, polynomial time approximation schemes, graph bisection, planar graphs},
URL = {http://link.aip.org/link/?SMJ/35/110/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lotker-Patt-Shamir-Pavlov-Peleg/05,
AUTHOR = {Lotker, Zvi and Patt-Shamir, Boaz and Pavlov, Elan and Peleg, David},
TITLE = {Minimum-weight spanning tree construction in $O(\log \log n)$ communication rounds},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {120-131},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {minimum-weight spanning tree, distributed algorithms},
URL = {http://link.aip.org/link/?SMJ/35/120/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Batu-Dasgupta-Kumar-Rubinfeld/05,
AUTHOR = {Batu, Tu{\v{g}}kan and Dasgupta, Sanjoy and Kumar, Ravi and Rubinfeld, Ronitt},
TITLE = {The complexity of approximating the entropy},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {132-150},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {entropy estimation, sublinear algorithms, properties of distributions, property testing},
URL = {http://link.aip.org/link/?SMJ/35/132/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gao-Zhang/05,
AUTHOR = {Gao, Jie and Zhang, Li},
TITLE = {Well-separated pair decomposition for the unit-disk graph metric and its applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {151-169},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {well-separated pair decomposition, unit-disk graph, approximation algorithm},
URL = {http://link.aip.org/link/?SMJ/35/151/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kuperberg/05,
AUTHOR = {Kuperberg, Greg},
TITLE = {A subexponential-time quantum algorithm for the dihedral hidden subgroup problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {170-188},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {quantum algorithm, dihedral hidden subgroup},
URL = {http://link.aip.org/link/?SMJ/35/170/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hassin-Levin/05b,
AUTHOR = {Hassin, Refael and Levin, Asaf},
TITLE = {A better-than-greedy approximation algorithm for the minimum set cover problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {189-200},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {greedy algorithm, approximation algorithms, set cover problem},
URL = {http://link.aip.org/link/?SMJ/35/189/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Amano-Maruoka/05a,
AUTHOR = {Amano, Kazuyuki and Maruoka, Akira},
TITLE = {A superpolynomial lower bound for a circuit computing the clique function with at most $(1/6)\log \log n$ negation gates},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {201-216},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {circuit complexity, monotone circuit, negation-limited circuit, approximation method, lower bound, clique function},
URL = {http://link.aip.org/link/?SMJ/35/201/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gennaro-Gertner-Katz-Trevisan/05,
AUTHOR = {Gennaro, Rosario and Gertner, Yael and Katz, Jonathan and Trevisan, Luca},
TITLE = {Bounds on the efficiency of generic cryptographic constructions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {217-246},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {lower bounds, pseudorandom generators, hash functions, digital signatures, encryption},
URL = {http://link.aip.org/link/?SMJ/35/217/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kortsarz-Nutov/05,
AUTHOR = {Kortsarz, Guy and Nutov, Zeev},
TITLE = {Approximating $k$-node connected subgraphs via critical graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {1},
PAGES = {247-257},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {connectivity, approximation, graphs, network design},
URL = {http://link.aip.org/link/?SMJ/35/247/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hlineny/05,
AUTHOR = {Hlin{\v{e}}n{\'y}, Petr},
TITLE = {A parametrized algorithm for matroid branch-width},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {259-277},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {representable matroid, parametrized algorithm, branch-width, rank-width},
URL = {http://link.aip.org/link/?SMJ/35/259/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Albers-Schmidt/05,
AUTHOR = {Albers, Susanne and Schmidt, Markus},
TITLE = {On the performance of greedy algorithms in packet buffering},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {278-304},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {buffer, competitive, greedy, network switch, online, packet, throughput},
URL = {http://link.aip.org/link/?SMJ/35/278/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Busch-Tirthapura/05,
AUTHOR = {Busch, Costas and Tirthapura, Srikanta},
TITLE = {Analysis of link reversal routing algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {305-326},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {link reversal routing, wireless networks, ad hoc networks, fault tolerance, self stabilization},
URL = {http://link.aip.org/link/?SMJ/35/305/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dalal-Devroye-Malalla-McLeish/05,
AUTHOR = {Dalal, Ketan and Devroye, Luc and Malalla, Ebrahim and McLeish, Erin},
TITLE = {Two-way chaining with reassignment},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {327-340},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {hashing, two-way chaining, worst-case search time, random graphs, probabilistic analysis of algorithms},
URL = {http://link.aip.org/link/?SMJ/35/327/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bender-Demaine-Farach-Colton/05,
AUTHOR = {Bender, Michael A. and Demaine, Erik D. and Farach-Colton, Martin},
TITLE = {Cache-oblivious $B$-trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {341-358},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {memory hierarchy, cache efficiency, data structures, search trees},
URL = {http://link.aip.org/link/?SMJ/35/341/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lee-Choe/05,
AUTHOR = {Lee, Gyung-Ok and Choe, Kwang-Moo},
TITLE = {A powerful $LL(k)$ covering transformation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {359-377},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {memory hierarchy, cache efficiency, data structures, search trees},
URL = {http://link.aip.org/link/?SMJ/35/341/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Grossi-Vitter/05,
AUTHOR = {Grossi, Roberto and Vitter, Jeffrey Scott},
TITLE = {Compressed suffix arrays and suffix trees with applications to text indexing and string matching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {378-407},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {compression, text indexing, text retrieval, compressed data structures, suffix arrays, suffix trees, string searching, pattern matching},
URL = {http://link.aip.org/link/?SMJ/35/378/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Friedman-Goerdt-Krivelevich/05,
AUTHOR = {Friedman, Joel and Goerdt, Andreas and Krivelevich, Michael},
TITLE = {Recognizing more unsatisfiable random $k$-SAT instances efficiently},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {408-430},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {random structures,random satisfiability, spectral methods},
URL = {http://link.aip.org/link/?SMJ/35/408/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Epstein-van_Stee/05c,
AUTHOR = {Epstein, Leah and van Stee, Rob},
TITLE = {Optimal online algorithms for multidimensional packing problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {431-448},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {multidimensional bin packing, online algorithms, optimal algorithms},
URL = {http://link.aip.org/link/?SMJ/35/431/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rasala-Wilfong/05,
AUTHOR = {Rasala, April and Wilfong, Gordon},
TITLE = {Strictly nonblocking WDM cross-connects},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {449-485},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {optical networking, cross-connect, wavelength division multiplexing, strictly nonblocking},
URL = {http://link.aip.org/link/?SMJ/35/449/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldberg-Martin-Paterson/05,
AUTHOR = {Goldberg, Leslie Ann and Martin, Russell and Paterson, Mike},
TITLE = {Strong spatial mixing with fewer colors for lattice graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {2},
PAGES = {486-517},
YEAR = {2005},
EDITOR = {Tardos, E.},
KEYWORDS = {strong spatial mixing, proper graph coloring, antiferromagnetic potts model},
URL = {http://link.aip.org/link/?SMJ/35/486/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jansen-Porkolab/06a,
AUTHOR = {Jansen, Klaus and Porkolab, Lorant},
TITLE = {General multiprocessor task scheduling: Approximate solutions in linear time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {519-530},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, scheduling problem, linear programming},
URL = {http://link.aip.org/link/?SMJ/35/519/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Arkin-Bender-Demaine-Fekete-Mitchell-Sethia/06,
AUTHOR = {Arkin, Esther M. and Bender, Michael A. and Demaine, Erik D. and Fekete, S{\'a}ndor P. and Mitchell, Joseph S.B. and Sethia, Saurabh},
TITLE = {Optimal covering tours with turn costs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {531-566},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {nc machining, np-completeness, turn costs, manufacturing, traveling salesman problem, milling, lawn mowing, covering, approximation algorithms, polynomial-time approximation scheme, $m$-guillotine subdivisions},
URL = {http://link.aip.org/link/?SMJ/35/531/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldstein-Kobayashi/06a,
AUTHOR = {Goldstein, Darin and Kobayashi, Kojiro},
TITLE = {On the complexity of network synchronization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {567-589},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {firing squad synchronization problem, network synchronization, distributed computation},
URL = {http://link.aip.org/link/?SMJ/35/567/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Doberkat/06a,
AUTHOR = {Doberkat, Ernst-Erich},
TITLE = {Stochastic relations: Congruences, bisimulations and the Hennessy-Milner theorem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {590-626},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {stochastic relations, stochastic kripke models, congruences, bisimulations, modal logic, hennessy--milner theorem},
URL = {http://link.aip.org/link/?SMJ/35/590/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chazelle-Liu-Magen/06,
AUTHOR = {Chazelle, Bernard and Liu, Ding and Magen, Avner},
TITLE = {Sublinear geometric algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {627-646},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {sublinear algorithms, approximate shortest paths, polyhedral intersection},
URL = {http://link.aip.org/link/?SMJ/35/627/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kjos-Hanssen-Nies-Stephan/06,
AUTHOR = {Kjos-Hanssen, Bj{\o}rn and Nies, Andr{\'e} and Stephan, Frank},
TITLE = {Lowness for the class of Schnorr random reals},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {647-657},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {lowness, randomness, schnorr randomness, turing degrees, recursion theory, computability theory},
URL = {http://link.aip.org/link/?SMJ/35/647/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Li-Yao/06,
AUTHOR = {Li, Minming and Yao, Frances F.},
TITLE = {An efficient algorithm for computing optimal discrete voltage schedules},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {658-671},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {scheduling, energy efficiency, variable voltage processor, discrete optimization},
URL = {http://link.aip.org/link/?SMJ/35/658/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Elkin-Kortsarz/06c,
AUTHOR = {Elkin, Michael and Kortsarz, Guy},
TITLE = {A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {672-689},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {directed, multicast, approximation, graph},
URL = {http://link.aip.org/link/?SMJ/35/672/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vertigan/06,
AUTHOR = {Vertigan, Dirk},
TITLE = {The computational complexity of Tutte invariants for planar graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {690-712},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {tutte polynomial, potts model, knot polynomials, planar graphs, computational complexity, polynomial time, $zp$-complete, enumeration, reliability, percolation},
URL = {http://link.aip.org/link/?SMJ/35/690/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chekuri-Khanna/06,
AUTHOR = {Chekuri, Chandra and Khanna, Sanjeev},
TITLE = {A polynomial time approximation scheme for the multiple knapsack problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {713-728},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {multiple knapsack problem, generalized assignment problem, polynomial time approximation scheme, approximation algorithm},
URL = {http://link.aip.org/link/?SMJ/35/713/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Shi-Su/06,
AUTHOR = {Shi, Weiping and Su, Chen},
TITLE = {The rectilinear Steiner arborescence problem is $NP$-complete},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {729-740},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {steiner tree, computational complexity, np-complete},
URL = {http://link.aip.org/link/?SMJ/35/729/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Wagh-Guzide/06,
AUTHOR = {Wagh, Meghanad D. and Guzide, Osman},
TITLE = {Mapping cycles and trees on wrap-around butterfly graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {741-765},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {butterfly graphs, mathematical model, finite field, mapping, cycles, trees},
URL = {http://link.aip.org/link/?SMJ/35/741/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ngo/06,
AUTHOR = {Ngo, Hung Q.},
TITLE = {WDM switching networks, rearrangeable and nonblocking $[w,f]$-connectors},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {3},
PAGES = {766-785},
YEAR = {2005-2006},
EDITOR = {Tardos, E.},
KEYWORDS = {wavelength division multiplexing, switching networks, $[w, f]$-connectors},
URL = {http://link.aip.org/link/?SMJ/35/766/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alon-Naor/06,
AUTHOR = {Alon, Noga and Naor, Assaf},
TITLE = {Approximating the cut-norm via Grothendieck's inequality},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {787-803},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {cut-norm, grothendieck's inequality, semidefinite programming, approximation algorithms, szemer\&eacute, di partitions},
URL = {http://link.aip.org/link/?SMJ/35/787/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Aaronson/06,
AUTHOR = {Aaronson, Scott},
TITLE = {Lower bounds for local search by quantum arguments},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {804-824},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {quantum computing, query complexity, decision trees, local search, local optima, polynomial local search, random walks},
URL = {http://link.aip.org/link/?SMJ/35/804/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bienstock-Iyengar/06,
AUTHOR = {Bienstock, D. and Iyengar, G.},
TITLE = {Approximating fractional packings and coverings in $O(1/\epsilon)$ iterations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {825-854},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithms, packing problems, multicommodity flows},
URL = {http://link.aip.org/link/?SMJ/35/825/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Beier-Vocking/06a,
AUTHOR = {Beier, Rene and V{\"o}cking, Berthold},
TITLE = {Typical properties of winners and losers in discrete optimization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {855-881},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {optimization problems, average-case analysis, smoothed analysis},
URL = {http://link.aip.org/link/?SMJ/35/855/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kelner/06,
AUTHOR = {Kelner, Jonathan A.},
TITLE = {Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {882-902},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {bounded genus, circle packing, graph separators, laplacian, partitioning, spectral partitioning},
URL = {http://link.aip.org/link/?SMJ/35/882/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Healy-Vadhan-Viola/06,
AUTHOR = {Healy, Alexander and Vadhan, Salil and Viola, Emanuele},
TITLE = {Using nondeterminism to amplify hardness},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {903-931},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {average-case complexity, hardness amplification, pseudorandom generators for space-bounded computation, noise stability},
URL = {http://link.aip.org/link/?SMJ/35/903/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Patrascu-Demaine/06,
AUTHOR = {P{\v{a}}tra{\c{s}}cu, Mihai and Demaine, Erik D.},
TITLE = {Logarithmic lower bounds in the cell-probe model},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {932-963},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {cell-probe complexity, lower bounds, data structures, dynamic graph problems, partial-sums problem},
URL = {http://link.aip.org/link/?SMJ/35/932/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feige/06,
AUTHOR = {Feige, Uriel},
TITLE = {On sums of independent random variables with unbounded variance and estimating the average degree in a graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {964-984},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {markov inequality, shortest paths},
URL = {http://link.aip.org/link/?SMJ/35/964/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lovasz-Vempala/06a,
AUTHOR = {Lov{\'a}sz, L{\'a}szl{\'o} and Vempala, Santosh},
TITLE = {Hit-and-run from a corner},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {4},
PAGES = {985-1005},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {sampling, random walks, isoperimetric inequalities},
URL = {http://link.aip.org/link/?SMJ/35/985/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Amir-Aumann-Lewenstein-Porat/06,
AUTHOR = {Amir, Amihood and Aumann, Yonatan and Lewenstein, Moshe and Porat, Ely},
TITLE = {Function matching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1007-1022},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {pattern matching, parameterized matching, function matching, color maps},
URL = {http://link.aip.org/link/?SMJ/35/1007/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Curran-Lee-Yu/06a,
AUTHOR = {Curran, Sean and Lee, Orlando and Yu, Xingxing},
TITLE = {Finding four independent trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1023-1058},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {connectivity, chain decomposition, numbering, independent trees, algorithm},
URL = {http://link.aip.org/link/?SMJ/35/1023/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Petersen-Robson/06,
AUTHOR = {Petersen, Holger and Robson, John Michael},
TITLE = {Efficient simulations by queue machines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1059-1069},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {pushdown automata, grammars, multiqueue machines, multitape machines, simulation, upper bounds},
URL = {http://link.aip.org/link/?SMJ/35/1059/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kempe-Kitaev-Regev/06,
AUTHOR = {Kempe, Julia and Kitaev, Alexei and Regev, Oded},
TITLE = {The complexity of the local Hamiltonian problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1070-1097},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {quantum computation, local hamiltonian problem, complete problems, adiabatic computation},
URL = {http://link.aip.org/link/?SMJ/35/1070/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jansson-Nguyen-Sung/06,
AUTHOR = {Jansson, Jesper and Nguyen, Nguyen Bao and Sung, Wing-Kin},
TITLE = {Algorithms for combining rooted triplets into a galled phylogenetic network},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1098-1121},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {phylogenetic network, galled network, rooted triplet, $sn$-tree, np-hardness, algorithm},
URL = {http://link.aip.org/link/?SMJ/35/1098/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Niggl-Wunderlich/06,
AUTHOR = {Niggl, Karl-Heinz and Wunderlich, Henning},
TITLE = {Certifying polynomial time and linear/polynomial space for imperative programs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1122-1147},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {polynomial time, linear space, polynomial space, static program analysis, property testing, implicit computational complexity, imperative programming languages},
URL = {http://link.aip.org/link/?SMJ/35/1122/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Har-Peled-Mendel/06,
AUTHOR = {Har-Peled, Sariel and Mendel, Manor},
TITLE = {Fast construction of nets in low-dimensional metrics and their applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1148-1184},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {doubling dimension, nearest neighbor search, approximate distance oracle, quadtree, metric nets, doubling measure, distance labeling},
URL = {http://link.aip.org/link/?SMJ/35/1148/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Reingold-Shaltiel-Wigderson/06,
AUTHOR = {Reingold, Omer and Shaltiel, Ronen and Wigderson, Avi},
TITLE = {Extracting randomness via repeated condensing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1185-1209},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {randomness extractors, randomness condensers, derandomization},
URL = {http://link.aip.org/link/?SMJ/35/1185/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lohrey/06,
AUTHOR = {Lohrey, Markus},
TITLE = {Word problems and membership problems on compressed words},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1210-1240},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {grammar-based compression, word problems for monoids, context-free languages, complexity},
URL = {http://link.aip.org/link/?SMJ/35/1210/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Queyranne-Schulz/06,
AUTHOR = {Queyranne, Maurice and Schulz, Andreas S.},
TITLE = {Approximation bounds for a general class of precedence constrained parallel machine scheduling problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1241-1253},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {approximation algorithm, linear programming relaxation, performance guarantee, precedence constraints, scheduling},
URL = {http://link.aip.org/link/?SMJ/35/1241/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Naor-Pinkas/06,
AUTHOR = {Naor, Moni and Pinkas, Benny},
TITLE = {Oblivious polynomial evaluation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {5},
PAGES = {1254-1281},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {cryptography, secure computation, noisy polynomial reconstruction},
URL = {http://link.aip.org/link/?SMJ/35/1254/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Weihrauch-Zhong/06a,
AUTHOR = {Weihrauch, Klaus and Zhong, Ning},
TITLE = {An algorithm for computing fundamental solutions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1283-1294},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {computable analysis, partial differential equations, fundamental solution},
URL = {http://link.aip.org/link/?SMJ/35/1283/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Abiteboul-Alstrup-Kaplan-Milo-Rauhe/06,
AUTHOR = {Abiteboul, Serge and Alstrup, Stephen and Kaplan, Haim and Milo, Tova and Rauhe, Theis},
TITLE = {Compact labeling scheme for ancestor queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1295-1309},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {ancestor queries, rooted tree, labeling algorithm, alphabetic codes},
URL = {http://link.aip.org/link/?SMJ/35/1295/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Durr-Heiligman-Hoyer-Mhalla/06,
AUTHOR = {D{\"u}rr, Christoph and Heiligman, Mark and H{\o}yer, Peter and Mhalla, Mehdi},
TITLE = {Quantum query complexity of some graph problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1310-1328},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {graph theory, quantum algorithm, lower bound, connectivity, minimum spanning tree, single source shortest paths},
URL = {http://link.aip.org/link/?SMJ/35/1310/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jonsson-Klasson-Krokhin/06,
AUTHOR = {Jonsson, Peter and Klasson, Mikael and Krokhin, Andrei},
TITLE = {The approximability of three-valued MAX CSP},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1329-1349},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {maximum constraint satisfaction, approximability, dichotomy, supermodularity},
URL = {http://link.aip.org/link/?SMJ/35/1329/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Berenbrink-Czumaj-Steger-Vocking/06,
AUTHOR = {Berenbrink, Petra and Czumaj, Artur and Steger, Angelika and V{\"o}cking, Berthold},
TITLE = {Balanced allocations: The heavily loaded case},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1350-1385},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {occupancy problems, balls-into-bins processes, randomized resource allocation},
URL = {http://link.aip.org/link/?SMJ/35/1350/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Geerts-Kuijpers-Van_den_Bussche/06,
AUTHOR = {Geerts, Floris and Kuijpers, Bart and Van den Bussche, Jan},
TITLE = {Linearization and completeness results for terminating transitive closure queries on spatial databases},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1386-1439},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {constraint databases, real algebraic geometry, transitive closure logics, query languages},
URL = {http://link.aip.org/link/?SMJ/35/1386/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chern-Hwang/06,
AUTHOR = {Chern, Hua-Huai and Hwang, Hsien-Kuei},
TITLE = {Partial match queries in random $k-d$ trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1440-1466},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {$k$-d trees, partial match queries, differential equations, average-case analysis of algorithms, method of linear operators, asymptotic analysis},
URL = {http://link.aip.org/link/?SMJ/35/1440/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Allender-Buhrman-Koucky-van_Melkebeek-Ronneburger/06,
AUTHOR = {Allender, Eric and Buhrman, Harry and Kouck{\'y}, Michal and van Melkebeek, Dieter and Ronneburger, Detlef},
TITLE = {Power from random strings},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1467-1493},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {kolmogorov complexity, completeness, reductions, randomness, derandomization},
URL = {http://link.aip.org/link/?SMJ/35/1467/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mortensen/06,
AUTHOR = {Mortensen, Christian Worm},
TITLE = {Fully dynamic orthogonal range reporting on RAM},
JOURNAL = {SIAM J. Comput.},
VOLUME = {35},
NUMBER = {6},
PAGES = {1494-1525},
YEAR = {2006},
EDITOR = {Tardos, E.},
KEYWORDS = {range searching, data structures, orthogonal},
URL = {http://link.aip.org/link/?SMJ/35/1494/1},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}