SIAM Journal on Computing, Volume 36

Volume 36, Number 1, 2006

• Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira:
  Scheduling Split Intervals. 1-15
  
• Andrei A. Bulatov, Víctor Dalmau:
  A Simple Algorithm for Mal'tsev Constraints. 16-27
  
• John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan:
  Identifying Clusters from Positive Data. 28-55
  
• Noa Agmon, David Peleg:
  Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots. 56-82
  
• Stasys Jukna:
  Disproving the Single Level Conjecture. 83-98
  
• Li-San Wang, Tandy Warnow:
  Reconstructing Chromosomal Evolution. 99-131
  
• Petros Drineas, Ravi Kannan, Michael W. Mahoney:
  Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. 132-157
  
• Petros Drineas, Ravi Kannan, Michael W. Mahoney:
  Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. 158-183
  
• Petros Drineas, Ravi Kannan, Michael W. Mahoney:
  Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition. 184-206
  
• Nadia Creignou, Bruno Zanuttini:
  A Complete Classification of the Complexity of Propositional Abduction. 207-229
  
• Tomás Feder, Pavol Hell:
  Full Constraint Satisfaction Problems. 230-246
  
• Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin:
  Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. 247-278
  
• Ichiro Suzuki, Masafumi Yamashita:
  Erratum: Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. 279-280
  

Volume 36, Number 2, 2006

• Fedor V. Fomin, Dimitrios M. Thilikos:
  Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up. 281-309
  
• Dieter Kratsch, Jeremy Spinrad:
  Between O(nm) and O(n^alpha). 310-325
  
• Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jeremy Spinrad:
  Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs. 326-353
  
• Yair Bartal, Amos Fiat, Stefano Leonardi:
  Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. 354-393
  
• Yossi Matias, Eran Segal, Jeffrey Scott Vitter:
  Efficient Bundle Sorting. 394-410
  
• Mohammad Mahdian, Yinyu Ye, Jiawei Zhang:
  Approximation Algorithms for Metric Facility Location Problems. 411-432
  
• Michael Elkin:
  An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. 433-456
  
• Gunnar Hoest, Nir Shavit:
  Toward a Topological Characterization of Asynchronous Complexity. 457-497
  
• Julia Chuzhoy, Joseph Naor:
  Covering Problems with Hard Capacities. 498-515
  
• Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta:
  Properties of NP-Complete Sets. 516-542
  
• Jon Feldman, Matthias Ruhl:
  The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. 543-561
  

Volume 36, Number 3, 2006

• Scott Diehl, Dieter van Melkebeek:
  Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. 563-594
  
• Richard Beigel, Lance Fortnow, Frank Stephan:
  Infinitely-Often Autoreducible Sets. 595-608
  
• Aravind Srinivasan:
  An Extension of the Lovász Local Lemma, and its Applications to Integer Programming. 609-634
  
• Guantao Chen, Zhicheng Gao, Xingxing Yu, Wenan Zang:
  Approximating Longest Cycles in Graphs with Bounded Degrees. 635-656
  
• Amit Kumar, Jon M. Kleinberg:
  Fairness Measures for Resource Allocation. 657-680
  
• Timothy M. Chan:
  Dynamic Subgraph Connectivity with Geometric Applications. 681-694
  
• Micha Sharir, Emo Welzl:
  On the Number of Crossing-Free Matchings, Cycles, and Partitions. 695-720
  
• Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink:
  Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm. 721-739
  
• Dimitris Achlioptas, Cristopher Moore:
  Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold. 740-762
  
• Wim van Dam, Sean Hallgren, Lawrence Ip:
  Quantum Algorithms for Some Hidden Shift Problems. 763-778
  
• Tali Kaufman, Dana Ron:
  Testing Polynomials over General Fields. 779-802
  
• Shmuel Safra:
  Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition. 803-814
  
• Pankaj K. Agarwal, Mark H. Overmars, Micha Sharir:
  Computing Maximally Separated Sets in the Plane. 815-834
  
• Tomasz Luczak, Jaroslav Nesetril:
  A Probabilistic Approach to the Dichotomy Problem. 835-843
  

Volume 36, Number 4, 2006

• Oded Goldreich, Madhu Sudan: Special Issue on Randomness and Complexity.
• Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
  Cryptography in NC⁰. 845-888
  
• Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
  Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. 889-974
  
• Irit Dinur, Omer Reingold:
  Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. 975-1024
  
• Subhash Khot:
  Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. 1025-1071
  
• Ariel Gabizon, Ran Raz, Ronen Shaltiel:
  Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. 1072-1094
  
• Boaz Barak, Russell Impagliazzo, Avi Wigderson:
  Extracting Randomness Using Few Independent Sources. 1095-1118
  
• Andrej Bogdanov, Luca Trevisan:
  On Worst-Case to Average-Case Reductions for NP Problems. 1119-1159
  
• Salil P. Vadhan:
  An Unconditional Study of Computational Zero Knowledge. 1160-1214
  
• Amir Shpilka, Avi Wigderson:
  Derandomizing Homomorphism Testing in General Groups. 1215-1230
  

Volume 36, Number 5, 2007

• Jesse Kamp, David Zuckerman:
  Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. 1231-1247
  
• Mikhail Alekhnovich, Eli Ben-Sasson:
  Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs. 1248-1263
  
• Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner:
  The Complexity of Computing the Size of an Interval. 1264-1300
  
• Dan Boneh, Ran Canetti, Shai Halevi, Jonathan Katz:
  Chosen-Ciphertext Security from Identity-Based Encryption. 1301-1328
  
• Yoko Kamidoi, Noriyoshi Yoshida, Hiroshi Nagamochi:
  A Deterministic Algorithm for Finding All Minimum k-Way Cuts. 1329-1341
  
• Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl:
  Online Conflict-Free Coloring for Intervals. 1342-1359
  
• David Eppstein, Michael T. Goodrich, Daniel S. Hirschberg:
  Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes. 1360-1375
  
• Julia Chuzhoy, Joseph Naor:
  The Hardness of Metric Labeling. 1376-1386
  
• Emanuele Viola:
  Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates. 1387-1403
  
• Zeev Dvir, Amir Shpilka:
  Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits. 1404-1434
  
• Alan M. Frieze, Gregory B. Sorkin:
  The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems. 1435-1452
  
• Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski:
  The Wake-Up Problem in MultiHop Radio Networks. 1453-1471
  
• Hartmut Klauck, Robert Spalek, Ronald de Wolf:
  Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. 1472-1493
  
• Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang:
  Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. 1494-1511
  

Volume 36, Number 6, 2007

• Cynthia Dwork, Moni Naor:
  Zaps and Their Applications. 1513-1543
  
• David Soloveichik, Erik Winfree:
  Complexity of Self-Assembled Shapes. 1544-1569
  
• Bart Kuijpers, Gabriel M. Kuper, Jan Paredaens, Luc Vandeurzen:
  First-Order Languages Expressing Constructible Spatial Database Queries. 1570-1599
  
• Lisa Fleischer, Martin Skutella:
  Quickest Flows Over Time. 1600-1630
  
• Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell:
  A Constant-Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding. 1631-1647
  
• Harold N. Gabow:
  Finding Paths and Cycles of Superpolylogarithmic Length. 1648-1671
  
• Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro:
  An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms. 1672-1695
  
• John M. Hitchcock:
  Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. 1696-1708
  
• Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý:
  Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. 1709-1728
  
• Leonard J. Schulman, Tal Mor, Yossi Weinstein:
  Physical Limits of Heat-Bath Algorithmic Cooling. 1729-1747
  
• Max A. Alekseyev, Pavel A. Pevzner:
  Whole Genome Duplications and Contracted Breakpoint Graphs. 1748-1763
  
• Kasturi R. Varadarajan, Srinivasan Venkatesh, Yinyu Ye, Jiawei Zhang:
  Approximating the Radii of Point Sets. 1764-1776
  
• Alin Bostan, Pierrick Gaudry, Éric Schost:
  Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier-Manin Operator. 1777-1806