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
Electronic Edition (link) BibTeX
Andrei A. Bulatov, Víctor Dalmau:
A Simple Algorithm for Mal'tsev Constraints. 16-27
Electronic Edition (link) BibTeX
John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan:
Identifying Clusters from Positive Data. 28-55
Electronic Edition (link) BibTeX
Noa Agmon, David Peleg:
Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots. 56-82
Electronic Edition (link) BibTeX
Stasys Jukna:
Disproving the Single Level Conjecture. 83-98
Electronic Edition (link) BibTeX
Li-San Wang, Tandy Warnow:
Reconstructing Chromosomal Evolution. 99-131
Electronic Edition (link) BibTeX
Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. 132-157
Electronic Edition (link) BibTeX
Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. 158-183
Electronic Edition (link) BibTeX
Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition. 184-206
Electronic Edition (link) BibTeX
Nadia Creignou, Bruno Zanuttini:
A Complete Classification of the Complexity of Propositional Abduction. 207-229
Electronic Edition (link) BibTeX
Tomás Feder, Pavol Hell:
Full Constraint Satisfaction Problems. 230-246
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
Ichiro Suzuki, Masafumi Yamashita:
Erratum: Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. 279-280
Electronic Edition (link) BibTeX

Volume 36, Number 2, 2006

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

Volume 36, Number 3, 2006

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

Volume 36, Number 4, 2006

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

Volume 36, Number 5, 2007

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

Volume 36, Number 6, 2007

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