SIAM Journal on Computing, Volume 37

Volume 37, Number 1, 2007

Frank Harary, Wolfgang Slany, Oleg Verbitsky:
On the Computational Complexity of the Forcing Chromatic Number. 1-19
Electronic Edition (link) BibTeX
Hartmut Klauck:
Lower Bounds for Quantum Communication Complexity. 20-46
Electronic Edition (link) BibTeX
Dorit Aharonov, Amnon Ta-Shma:
Adiabatic Quantum State Generation. 47-82
Electronic Edition (link) BibTeX
Phillip G. Bradford, Michael N. Katehakis:
A Probabilistic Study on Combinatorial Expanders and Hashing. 83-111
Electronic Edition (link) BibTeX
Matthew Andrews, Lisa Zhang:
Hardness of the Undirected Congestion Minimization Problem. 112-131
Electronic Edition (link) BibTeX
Florent R. Madelaine, Iain A. Stewart:
Constraint Satisfaction, Logic and Forbidden Patterns. 132-163
Electronic Edition (link) BibTeX
Dimitris Achlioptas, Vladlen Koltun: Special Section on Foundations of Computer Science. 165 BibTeX
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev:
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. 166-194
Electronic Edition (link) BibTeX
Qi Cheng, Daqing Wan:
On the List and Bounded Distance Decodability of Reed-Solomon Codes. 195-209
Electronic Edition (link) BibTeX
Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness. 210-239
Electronic Edition (link) BibTeX
Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost. 240-251
Electronic Edition (link) BibTeX
Steve Chien, Alistair Sinclair:
Algebras with Polynomial Identities and Computing the Determinant. 252-266
Electronic Edition (link) BibTeX
Daniele Micciancio, Oded Regev:
Worst-Case to Average-Case Reductions Based on Gaussian Measures. 267-302
Electronic Edition (link) BibTeX
Kamal Jain:
A Polynomial Time Algorithm for Computing an Arrow-Debreu Market Equilibrium for Linear Utilities. 303-318
Electronic Edition (link) BibTeX
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?. 319-357
Electronic Edition (link) BibTeX

Volume 37, Number 2, 2007

A. Pavan, Srikanta Tirthapura:
Range-Efficient Counting of Distinct Elements in a Massive Data Stream. 359-379
Electronic Edition (link) BibTeX
Boaz Barak, Shien Jin Ong, Salil P. Vadhan:
Derandomization in Cryptography. 380-400
Electronic Edition (link) BibTeX
Gregory Mounie, Christophe Rapine, Denis Trystram:
A 3/2-Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks. 401-412
Electronic Edition (link) BibTeX
Frédéric Magniez, Miklos Santha, Mario Szegedy:
Quantum Algorithms for the Triangle Problem. 413-424
Electronic Edition (link) BibTeX
Yuri Gurevich, Paul Schupp:
Membership Problem for the Modular Group. 425-459
Electronic Edition (link) BibTeX
Anna Moss, Yuval Rabani:
Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems. 460-481
Electronic Edition (link) BibTeX
Eldar Fischer, Ilan Newman:
Testing versus Estimation of Graph Properties. 482-501
Electronic Edition (link) BibTeX
Amitabha Roy, Howard Straubing:
Definability of Languages by Generalized First-Order Formulas over N⁺. 502-521
Electronic Edition (link) BibTeX
Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sue Whitesides:
Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra. 522-551
Electronic Edition (link) BibTeX
Hartmut Klauck:
One-Way Communication Complexity and the Ne[c-caron]iporuk Lower Bound on Formula Size. 552-583
Electronic Edition (link) BibTeX
Sunil Arya, Theocharis Malamatos, David M. Mount, Ka Chun Wong:
Optimal Expected-Case Planar Point Location. 584-610
Electronic Edition (link) BibTeX
Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha:
Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates. 611-629
Electronic Edition (link) BibTeX
Naveen Garg, Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. 630-652
Electronic Edition (link) BibTeX
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff:
Approximation Algorithms for Orienteering and Discounted-Reward TSP. 653-670
Electronic Edition (link) BibTeX

Volume 37, Number 3, 2007

Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo:
Effective Strong Dimension in Algorithmic Information and Computational Complexity. 671-705
Electronic Edition (link) BibTeX
Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, Martin Skutella:
New Approaches for Virtual Private Network Design. 706-721
Electronic Edition (link) BibTeX
Partha Dutta, Rachid Guerraoui, Bastian Pochon:
The Time-Complexity of Local Decision in Distributed Agreement. 722-756
Electronic Edition (link) BibTeX
Stavros G. Kolliopoulos, Satish Rao:
A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem. 757-782
Electronic Edition (link) BibTeX
William Aiello, Frank Thomson Leighton:
Hamming Codes, Hypercube Embeddings, and Fault Tolerance. 783-803
Electronic Edition (link) BibTeX
Assaf Naor, Gideon Schechtman:
Planar Earthmover Is Not in L₁. 804-826
Electronic Edition (link) BibTeX
Ryan O'Donnell, Rocco A. Servedio:
Learning Monotone Decision Trees in Polynomial Time. 827-844
Electronic Edition (link) BibTeX
Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. 845-869
Electronic Edition (link) BibTeX
José R. Correa, Michel X. Goemans:
Improved Bounds on Nonblocking 3-Stage Clos Networks. 870-894
Electronic Edition (link) BibTeX
Michael Molloy, Mohammad R. Salavatipour:
The Resolution Complexity of Random Constraint Satisfaction Problems. 895-922
Electronic Edition (link) BibTeX
Xujin Chen, Xiaodong Hu, Wenan Zang:
A Min-Max Theorem on Tournaments. 923-937
Electronic Edition (link) BibTeX
Cristopher Moore, Daniel N. Rockmore, Alexander Russell, Leonard J. Schulman:
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts. 938-958
Electronic Edition (link) BibTeX
Noga Alon, Eldar Fischer, Ilan Newman:
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. 959-976
Electronic Edition (link) BibTeX

Volume 37, Number 4, 2007

Nancy A. Lynch, Roberto Segala, Frits W. Vaandrager:
Observing Branching Structure through Probabilistic Contexts. 977-1013
Electronic Edition (link) BibTeX
Bin Fu, Wei Wang:
Geometric Separators and Their Applications to Protein Folding in the HP-Model. 1014-1029
Electronic Edition (link) BibTeX
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn:
Popular Matchings. 1030-1045
Electronic Edition (link) BibTeX
David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. 1046-1056
Electronic Edition (link) BibTeX