SIAM Journal on Computing, Volume 38

Volume 38, Number 1, 2008

Nir Halman:
On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model. 1-45
Electronic Edition (link) BibTeX
Sophie Laplante, Frédéric Magniez:
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. 46-62
Electronic Edition (link) BibTeX
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC⁰ Circuits Given a Truth Table. 63-84
Electronic Edition (link) BibTeX
Anna Pagh, Rasmus Pagh:
Uniform Hashing in Constant Time and Optimal Space. 85-96
Electronic Edition (link) BibTeX
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith:
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. 97-139
Electronic Edition (link) BibTeX
Dana Moshkovitz, Ran Raz:
Sub-Constant Error Low Degree Test of Almost-Linear Size. 140-180
Electronic Edition (link) BibTeX
Bodo Manthey:
On Approximating Restricted Cycle Covers. 181-206
Electronic Edition (link) BibTeX
Eldar Fischer, Arie Matsliah:
Testing Graph Isomorphism. 207-225
Electronic Edition (link) BibTeX
Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
Improving the Stretch Factor of a Geometric Network by Edge Augmentation. 226-240
Electronic Edition (link) BibTeX
Kamal Jain, Vijay V. Vazirani:
Equitable Cost Allocations via Primal--Dual-Type Algorithms. 241-256
Electronic Edition (link) BibTeX
Mark de Berg, Chris Gray:
Vertical Ray Shooting and Computing Depth Orders for Fat Objects. 257-275
Electronic Edition (link) BibTeX
Reuven Cohen, David Peleg:
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. 276-302
Electronic Edition (link) BibTeX
Vasco Brattka:
Plottable Real Number Functions and the Computable Graph Theorem. 303-328
Electronic Edition (link) BibTeX
Peter Jonsson, Fredrik Kuivinen, Gustav Nordh:
MAX ONES Generalized to Larger Domains. 329-365
Electronic Edition (link) BibTeX
Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
Exponential Separation of Quantum and Classical One-Way Communication Complexity. 366-384
Electronic Edition (link) BibTeX
Ke Chen, Sariel Har-Peled:
The Euclidean Orienteering Problem Revisited. 385-397
Electronic Edition (link) BibTeX
János Balogh, József Békési, Gábor Galambos, Gerhard Reinelt:
Lower Bound for the Online Bin Packing Problem with Restricted Repacking. 398-410
Electronic Edition (link) BibTeX
Leah Epstein, Asaf Levin:
An APTAS for Generalized Cost Variable-Sized Bin Packing. 411-428
Electronic Edition (link) BibTeX
Csaba D. Tóth:
Binary Space Partitions for Axis-Aligned Fat Rectangles. 429-447
Electronic Edition (link) BibTeX

Volume 38, Number 2, 2008

STOC 2005

Vladimir Trifonov:
An O(logn loglogn) Space Algorithm for Undirected st-Connectivity. 449-483
Electronic Edition (link) BibTeX
Ben Morris:
The Mixing Time of the Thorp Shuffle. 484-504
Electronic Edition (link) BibTeX
Noga Alon, Asaf Shapira:
Every Monotone Graph Property Is Testable. 505-522
Electronic Edition (link) BibTeX
Saurabh Sanghvi, Salil P. Vadhan:
The Round Complexity of Two-Party Random Selection. 523-550
Electronic Edition (link) BibTeX
Eli Ben-Sasson, Madhu Sudan:
Short PCPs with Polylog Query Complexity. 551-607
Electronic Edition (link) BibTeX
Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
Lower-Stretch Spanning Trees. 608-628
Electronic Edition (link) BibTeX
Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators. 629-657
Electronic Edition (link) BibTeX
Mikolaj Bojanczyk, Thomas Colcombet:
Tree-Walking Automata Do Not Recognize All Regular Languages. 658-701
Electronic Edition (link) BibTeX
Rafael Pass, Alon Rosen:
New and Improved Constructions of Nonmalleable Cryptographic Protocols. 702-752
Electronic Edition (link) BibTeX

Volume 38, Number 3, 2008

Yaoyun Shi, Yufan Zhu:
Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement. 753-766
Electronic Edition (link) BibTeX
Anil Maheshwari, Norbert Zeh:
I/O-Efficient Planar Separators. 767-801
Electronic Edition (link) BibTeX
Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
Approximate Shortest Paths in Anisotropic Regions. 802-824
Electronic Edition (link) BibTeX
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio:
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover. 825-840
Electronic Edition (link) BibTeX
Marcelo Arenas, Wenfei Fan, Leonid Libkin:
On the Complexity of Verifying Consistency of XML Specifications. 841-880
Electronic Edition (link) BibTeX
Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen:
Competitive Online Approximation of the Optimal Search Ratio. 881-898
Electronic Edition (link) BibTeX
Boris Aronov, Sariel Har-Peled:
On Approximating the Depth and Related Problems. 899-921
Electronic Edition (link) BibTeX
Àngel J. Gil, Miki Hermann, Gernot Salzer, Bruno Zanuttini:
Efficient Algorithms for Description Problems over Finite Totally Ordered Domains. 922-945
Electronic Edition (link) BibTeX
C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, Louxin Zhang:
Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment. 946-962
Electronic Edition (link) BibTeX
Igor L. Markov, Yaoyun Shi:
Simulating Quantum Computation by Contracting Tensor Networks. 963-981
Electronic Edition (link) BibTeX
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin:
Efficient Colored Orthogonal Range Counting. 982-1011
Electronic Edition (link) BibTeX
Petr Hlinený, Sang-il Oum:
Finding Branch-Decompositions and Rank-Decompositions. 1012-1032
Electronic Edition (link) BibTeX
Parikshit Gopalan:
Query-Efficient Algorithms for Polynomial Interpolation over Composites. 1033-1057
Electronic Edition (link) BibTeX
Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger:
Exact Algorithms for Treewidth and Minimum Fill-In. 1058-1079
Electronic Edition (link) BibTeX
Jack H. Lutz, Elvira Mayordomo:
Dimensions of Points in Self-Similar Fractals. 1080-1112
Electronic Edition (link) BibTeX
Jordi Levy, Manfred Schmidt-Schauß, Mateu Villaret:
The Complexity of Monadic Second-Order Unification. 1113-1140
Electronic Edition (link) BibTeX
Ravindran Kannan, Hadi Salmasian, Santosh Vempala:
The Spectral Method for General Mixture Models. 1141-1156
Electronic Edition (link) BibTeX
Nikhil Bansal, Don Coppersmith, Maxim Sviridenko:
Improved Approximation Algorithms for Broadcast Scheduling. 1157-1174
Electronic Edition (link) BibTeX
Ketan Mulmuley, Milind A. Sohoni:
Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. 1175-1206
Electronic Edition (link) BibTeX

Volume 38, Number 4, 2008

Dorit Aharonov, Michael Ben-Or:
Fault-Tolerant Quantum Computation with Constant Error Rate. 1207-1282
Electronic Edition (link) BibTeX
Sanjay Jain, Frank Stephan:
Mitotic Classes in Inductive Inference. 1283-1299
Electronic Edition (link) BibTeX
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung:
On Monotone Formula Composition of Perfect Zero-Knowledge Languages. 1300-1329
Electronic Edition (link) BibTeX
Jon M. Kleinberg, Mark Sandler, Aleksandrs Slivkins:
Network Failure Detection and Graph Connectivity. 1330-1346
Electronic Edition (link) BibTeX
Michael Alekhnovich, Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable. 1347-1363
Electronic Edition (link) BibTeX