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
Albert Atserias, Anuj Dawar, Martin Grohe:
Preservation under Extensions on Well-Behaved Finite Structures. 1364-1381
Electronic Edition (link) BibTeX
Dániel Marx:
Closest Substring Problems with Small Distances. 1382-1410
Electronic Edition (link) BibTeX
Ivan D. Baev, Rajmohan Rajaraman, Chaitanya Swamy:
Approximation Algorithms for Data Placement Problems. 1411-1429
Electronic Edition (link) BibTeX
Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn:
Faster Algorithms for Minimum Cycle Basis in Directed Graphs. 1430-1447
Electronic Edition (link) BibTeX
Subhash Khot, Assaf Naor:
Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies. 1448-1463
Electronic Edition (link) BibTeX
Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour:
Combination Can Be Hard: Approximability of the Unique Coverage Problem. 1464-1483
Electronic Edition (link) BibTeX
Shuji Kijima, Tomomi Matsui:
Approximation Algorithm and Perfect Sampler for Closed Jackson Networks with Single Servers. 1484-1503
Electronic Edition (link) BibTeX
Lusheng Wang, Yu Lin, Xiaowen Liu:
Approximation Algorithms for Biclustering Problems. 1504-1518
Electronic Edition (link) BibTeX
Marcin Jurdzinski, Mike Paterson, Uri Zwick:
A Deterministic Subexponential Algorithm for Solving Parity Games. 1519-1532
Electronic Edition (link) BibTeX
Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert Endre Tarjan, Jeffery Westbrook:
Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems. 1533-1573
Electronic Edition (link) BibTeX
Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers:
The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. 1574-1601
Electronic Edition (link) BibTeX
Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden:
The Price of Stability for Network Design with Fair Cost Allocation. 1602-1623
Electronic Edition (link) BibTeX
Ran Raz, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. 1624-1647
Electronic Edition (link) BibTeX
Adam Meyerson, Kamesh Munagala, Serge A. Plotkin:
Cost-Distance: Two Metric Network Design. 1648-1659
Electronic Edition (link) BibTeX

Volume 38, Number 5, 2008

Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. 1661-1694
Electronic Edition (link) BibTeX
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf:
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. 1695-1708
Electronic Edition (link) BibTeX
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang:
Graph Distances in the Data-Stream Model. 1709-1727
Electronic Edition (link) BibTeX
Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb:
Private Approximation of Search Problems. 1728-1760
Electronic Edition (link) BibTeX
Yuval Emek, David Peleg:
Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs. 1761-1781
Electronic Edition (link) BibTeX

Volume 38, Number 5, 2009

Libor Barto, Marcin Kozik, Todd Niven:
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell). 1782-1802
Electronic Edition (link) BibTeX
Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid:
Spanners of Complete k-Partite Geometric Graphs. 1803-1820
Electronic Edition (link) BibTeX
GaHyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski:
Profiles of Tries. 1821-1880
Electronic Edition (link) BibTeX
Umberto Straccia, Manuel Ojeda-Aciego, Carlos Viegas Damásio:
On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs. 1881-1911
Electronic Edition (link) BibTeX
Ulrich Schmid, Bettina Weiss, Idit Keidar:
Impossibility Results and Lower Bounds for Consensus under Link Failures. 1912-1951
Electronic Edition (link) BibTeX
Kiran S. Kedlaya, Sergey Yekhanin:
Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. 1952-1969
Electronic Edition (link) BibTeX
Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Weighted Boolean CSP. 1970-1986
Electronic Edition (link) BibTeX
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. 1987-2006
Electronic Edition (link) BibTeX
Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle:
Interval Completion Is Fixed Parameter Tractable. 2007-2020
Electronic Edition (link) BibTeX
Wouter Gelade, Wim Martens, Frank Neven:
Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. 2021-2043
Electronic Edition (link) BibTeX
Sudipto Guha, Andrew McGregor:
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams. 2044-2059
Electronic Edition (link) BibTeX
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney:
Sampling Algorithms and Coresets for $\ell_p Regression. 2060-2078
Electronic Edition (link) BibTeX
Holger Spakowski, Rahul Tripathi:
Hierarchical Unambiguity. 2079-2112
Electronic Edition (link) BibTeX

Volume 38, Number 6, 2009

Alexander A. Sherstov:
SeparatingAC⁰ from Depth-2 Majority Circuits. 2113-2129
Electronic Edition (link) BibTeX
Amir Shpilka:
Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. 2130-2161
Electronic Edition (link) BibTeX
Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung:
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. 2162-2178
Electronic Edition (link) BibTeX
Mee Yee Chan, Wun-Tat Chan, Francis Y. L. Chin, Stanley P. Y. Fung, Ming-Yang Kao:
Linear-Time Haplotype Inference on Pedigrees without Recombinations and Mating Loops. 2179-2197
Electronic Edition (link) BibTeX
Jing Xiao, Lan Liu, Lirong Xia, Tao Jiang:
Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations. 2198-2219
Electronic Edition (link) BibTeX
Louay M. J. Bazzi:
Polylogarithmic Independence Can Fool DNF Formulas. 2220-2272
Electronic Edition (link) BibTeX
Susanne Albers:
On the Value of Coordination in Network Design. 2273-2302
Electronic Edition (link) BibTeX
T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Aleksandrs Slivkins:
Metric Embeddings with Relaxed Guarantees. 2303-2329
Electronic Edition (link) BibTeX
Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. 2330-2355
Electronic Edition (link) BibTeX
Leonard M. Adleman, Jarkko Kari, Lila Kari, Dustin Reishus, Petr Sosík:
The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly. 2356-2381
Electronic Edition (link) BibTeX
David J. Aldous, Charles Bordenave, Marc Lelarge:
Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions. 2382-2410
Electronic Edition (link) BibTeX
Luc Devroye, James King, Colin McDiarmid:
Random Hyperplane Search Trees. 2411-2425
Electronic Edition (link) BibTeX
Sudipto Guha, Adam Meyerson, Kamesh Munagala:
A Constant Factor Approximation for the Single Sink Edge Installation Problem. 2426-2442
Electronic Edition (link) BibTeX
Marcin Kozik:
A 2EXPTIME Complete Varietal Membership Problem. 2443-2467
Electronic Edition (link) BibTeX
Baruch Awerbuch, Rohit Khandekar:
Stateless Distributed Gradient Descent for Positive Linear Programs. 2468-2486
Electronic Edition (link) BibTeX
Robert Krauthgamer, Yuval Rabani:
Improved Lower Bounds for Embeddings intoL₁$. 2487-2498
Electronic Edition (link) BibTeX
Artur Czumaj, Asaf Shapira, Christian Sohler:
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. 2499-2510
Electronic Edition (link) BibTeX