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

Volume 37, Number 2, 2007

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

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
  
• Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, Martin Skutella:
  New Approaches for Virtual Private Network Design. 706-721
  
• Partha Dutta, Rachid Guerraoui, Bastian Pochon:
  The Time-Complexity of Local Decision in Distributed Agreement. 722-756
  
• Stavros G. Kolliopoulos, Satish Rao:
  A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem. 757-782
  
• William Aiello, Frank Thomson Leighton:
  Hamming Codes, Hypercube Embeddings, and Fault Tolerance. 783-803
  
• Assaf Naor, Gideon Schechtman:
  Planar Earthmover Is Not in L₁. 804-826
  
• Ryan O'Donnell, Rocco A. Servedio:
  Learning Monotone Decision Trees in Polynomial Time. 827-844
  
• Paul Beame, Toniann Pitassi, Nathan Segerlind:
  Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. 845-869
  
• José R. Correa, Michel X. Goemans:
  Improved Bounds on Nonblocking 3-Stage Clos Networks. 870-894
  
• Michael Molloy, Mohammad R. Salavatipour:
  The Resolution Complexity of Random Constraint Satisfaction Problems. 895-922
  
• Xujin Chen, Xiaodong Hu, Wenan Zang:
  A Min-Max Theorem on Tournaments. 923-937
  
• 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
  
• Noga Alon, Eldar Fischer, Ilan Newman:
  Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. 959-976
  

Volume 37, Number 4, 2007

• Nancy A. Lynch, Roberto Segala, Frits W. Vaandrager:
  Observing Branching Structure through Probabilistic Contexts. 977-1013
  
• Bin Fu, Wei Wang:
  Geometric Separators and Their Applications to Protein Folding in the HP-Model. 1014-1029
  
• David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn:
  Popular Matchings. 1030-1045
  
• David P. Woodruff, Sergey Yekhanin:
  A Geometric Approach to Information-Theoretic Private Information Retrieval. 1046-1056
  
• Lior Davidovitch, Shlomi Dolev, Sergio Rajsbaum:
  Stability of Multivalued Continuous Consensus. 1057-1076
  
• Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia:
  Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size. 1077-1106
  
• Shirley Halevy, Eyal Kushilevitz:
  Distribution-Free Property-Testing. 1107-1138
  
• Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas:
  Universal Bufferless Packet Switching. 1139-1162
  
• Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, Russell A. Martin:
  Distributed Selfish Load Balancing. 1163-1181
  
• Tetsuo Asano, Jirí Matousek, Takeshi Tokuyama:
  Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge. 1182-1198
  
• Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, Tathagata Ray:
  Sampling and Meshing a Surface with Guaranteed Topology and Geometry. 1199-1227
  
• Yijia Chen, Martin Grohe:
  An Isomorphism Between Subexponential and Parameterized Complexity Theory. 1228-1258
  
• Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton:
  Localized Client-Server Load Balancing without Global Information. 1259-1279
  
• Guey-Yun Chang, Gen-Huey Chen:
  (t, k)-Diagnosability of Multiprocessor Systems with Applications to Grids and Tori. 1280-1298
  

Volume 37, Number 5, 2008

• Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, Vijaya Ramachandran:
  Oracles for Distances Avoiding a Failed Node or Link. 1299-1318
  
• Jochen Könemann, Stefano Leonardi, Guido Schäfer, Stefan H. M. van Zwam:
  A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game. 1319-1341
  
• Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer:
  The Forgetron: A Kernel-Based Perceptron on a Budget. 1342-1372
  
• Bradford G. Nickerson, Qingxiu Shi:
  On k-d Range Search with Patricia Tries. 1373-1386
  
• Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
  Quantum Property Testing. 1387-1400
  
• Karl Rubin, Alice Silverberg:
  Compression in Finite Fields and Torus-Based Cryptography. 1401-1428
  
• Ivona Bezáková, Daniel Stefankovic, Vijay V. Vazirani, Eric Vigoda:
  Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems. 1429-1454
  
• Liam Roditty, Uri Zwick:
  Improved Dynamic Reachability Algorithms for Directed Graphs. 1455-1471
  
• Aaron Archer, Asaf Levin, David P. Williamson:
  A Faster, Better Approximation Algorithm for the Minimum Latency Problem. 1472-1498
  
• John Augustine, Sandy Irani, Chaitanya Swamy:
  Optimal Power-Down Strategies. 1499-1516
  
• Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang:
  Splitting NP-Complete Sets. 1517-1535
  
• Jon Feldman, Ryan O'Donnell, Rocco A. Servedio:
  Learning Mixtures of Product Distributions over Discrete Domains. 1536-1564
  
• Leslie G. Valiant:
  Holographic Algorithms. 1565-1594
  
• Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu:
  Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling. 1595-1612
  
• Hagit Attiya, David Hay:
  Randomization Does Not Reduce the Average Delay in Parallel Packet Switches. 1613-1636
  
• Andrew V. Goldberg:
  A Practical Shortest Path Algorithm with Linear Expected Time. 1637-1655
  
• Elliot Anshelevich, David Kempe, Jon M. Kleinberg:
  Stability of Load Balancing Algorithms in Dynamic Adversarial Systems. 1656-1673
  
• Hubie Chen:
  The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case. 1674-1701
  

Volume 37, Number 6, 2008

• Irit Dinur, Éva Tardos: Special Issue on Foundations of Computer Science.
• Noga Alon, Asaf Shapira:
  A Characterization of the (Natural) Graph Properties Testable with One-Sided Error. 1703-1727
  
• Penny E. Haxell, Brendan Nagle, Vojtech Rödl:
  An Algorithmic Version of the Hypergraph Regularity Method. 1728-1776
  
• Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio:
  Agnostically Learning Halfspaces. 1777-1805
  
• Navin Goyal, Guy Kindler, Michael E. Saks:
  Lower Bounds for the Noisy Broadcast Problem. 1806-1841
  
• Cristopher Moore, Alexander Russell, Leonard J. Schulman:
  The Symmetric Group Defies Strong Fourier Sampling. 1842-1864
  
• Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner:
  Cryptography in the Bounded-Quantum-Storage Model. 1865-1890
  
• Rafael Pass, Alon Rosen:
  Concurrent Nonmalleable Commitments. 1891-1925
  
• Philip N. Klein:
  A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. 1926-1952