SIAM Journal on Computing, Volume 34

Volume 34, Number 1, 2004

Karhan Akcoglu, Petros Drineas, Ming-Yang Kao:
Fast Universalization of Investment Strategies. 1-22
Electronic Edition (link) BibTeX
Michal Katz, Nir A. Katz, Amos Korman, David Peleg:
Labeling Schemes for Flow and Connectivity. 23-40
Electronic Edition (link) BibTeX
Carme Àlvarez, Maria J. Blesa, Maria J. Serna:
A Characterization of Universal Stability in the Adversarial Queuing Model. 41-66
Electronic Edition (link) BibTeX
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. 67-88
Electronic Edition (link) BibTeX
Lars Ivansson, Jens Lagergren:
Algorithms for RH Mapping: New Ideas and Improved Analysis. 89-108
Electronic Edition (link) BibTeX
Stefan Hougardy, Annegret Wagler:
Perfectness is an Elusive Graph Property. 109-117
Electronic Edition (link) BibTeX
Daniele Micciancio:
Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor. 118-169
Electronic Edition (link) BibTeX
John M. Hitchcock:
Small Spans in Scaled Dimension. 170-194
Electronic Edition (link) BibTeX
Ben Morris, Alistair Sinclair:
Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. 195-226
Electronic Edition (link) BibTeX
Edith Cohen, Haim Kaplan:
Balanced-Replication Algorithms for Distribution Trees. 227-247
Electronic Edition (link) BibTeX
Yair Bartal, Manor Mendel:
Multiembedding of Metric Spaces. 248-259
Electronic Edition (link) BibTeX

Volume 34, Number 2, 2004

Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. 261-276
Electronic Edition (link) BibTeX
Markus Bläser:
A Complete Characterization of the Algebras of Minimal Bilinear Complexity. 277-298
Electronic Edition (link) BibTeX
Benjamin Doerr:
Nonindependent Randomized Rounding and an Application to Digital Halftoning. 299-317
Electronic Edition (link) BibTeX
Rajat Bhattacharjee, Ashish Goel, Zvi Lotker:
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. 318-332
Electronic Edition (link) BibTeX
Tushar Deepak Chandra, Vassos Hadzilacos, Prasad Jayanti, Sam Toueg:
Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus. 333-357
Electronic Edition (link) BibTeX
Gruia Calinescu, Howard J. Karloff, Yuval Rabani:
Approximation Algorithms for the 0-Extension Problem. 358-372
Electronic Edition (link) BibTeX
Kai-min Chung, Hsueh-I Lu:
An Optimal Algorithm for the Maximum-Density Segment Problem. 373-387
Electronic Edition (link) BibTeX
Satish Rao, Andréa W. Richa:
New Approximation Techniques for Some Linear Ordering Problems. 388-404
Electronic Edition (link) BibTeX
Mikkel Thorup:
Quick k-Median, k-Center, and Facility Location for Sparse Graphs. 405-432
Electronic Edition (link) BibTeX
S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke:
Online Scheduling to Minimize Average Stretch. 433-452
Electronic Edition (link) BibTeX
Anupam Gupta, Amit Kumar, Rajeev Rastogi:
Traveling with a Pez Dispenser (or, Routing Issues in MPLS). 453-474
Electronic Edition (link) BibTeX
Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler:
The Simplex Algorithm in Dimension Three. 475-497
Electronic Edition (link) BibTeX
Yasunori Ishihara, Shin Ishii, Hiroyuki Seki, Minoru Ito:
Temporal Reasoning about Two Concurrent Sequences of Events. 498-513
Electronic Edition (link) BibTeX

Volume 34, Number 3, 2005

Raimund Seidel, Micha Sharir:
Top-Down Analysis of Path Compression. 515-525
Electronic Edition (link) BibTeX
Pankaj K. Agarwal, Micha Sharir:
Pseudo-Line Arrangements: Duality, Algorithms, and Applications. 526-552
Electronic Edition (link) BibTeX
Vida Dujmovic, Pat Morin, David R. Wood:
Layout of Graphs with Bounded Tree-Width. 553-579
Electronic Edition (link) BibTeX
Artur Czumaj, Christian Sohler:
Abstract Combinatorial Programs and Efficient Property Testers. 580-615
Electronic Edition (link) BibTeX
Aris Anagnostopoulos, Adam Kirsch, Eli Upfal:
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input. 616-639
Electronic Edition (link) BibTeX
Nicolò Cesa-Bianchi, Alex Conconi, Claudio Gentile:
A Second-Order Perceptron Algorithm. 640-668
Electronic Edition (link) BibTeX
Ho-Leung Chan, Tak Wah Lam, Kar-Keung To:
Nonmigratory Online Deadline Scheduling on Multiprocessors. 669-682
Electronic Edition (link) BibTeX
Huaming Zhang, Xin He:
On Even Triangulations of 2-Connected Embedded Graphs. 683-696
Electronic Edition (link) BibTeX
Bala Kalyanasundaram, Kirk Pruhs:
Fault-Tolerant Scheduling. 697-719
Electronic Edition (link) BibTeX
Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin:
Classifying the Complexity of Constraints Using Finite Algebras. 720-742
Electronic Edition (link) BibTeX
Yumei Huo, Joseph Y.-T. Leung:
Online Scheduling of Precedence Constrained Tasks. 743-762
Electronic Edition (link) BibTeX
Jochen Könemann, R. Ravi:
Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds. 763-773
Electronic Edition (link) BibTeX

Volume 34, Number 4, 2005

Alon Efrat:
The Complexity of the Union of (alpha, beta)-Covered Objects. 775-787
Electronic Edition (link) BibTeX
Martin Skutella, Marc Uetz:
Stochastic Machine Scheduling with Precedence Constraints. 788-802
Electronic Edition (link) BibTeX
Moses Charikar, Sudipto Guha:
Improved Combinatorial Algorithms for Facility Location Problems. 803-824
Electronic Edition (link) BibTeX
Derek G. Corneil, Udi Rotics:
On the Relationship Between Clique-Width and Treewidth. 825-847
Electronic Edition (link) BibTeX
Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman:
Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups. 848-862
Electronic Edition (link) BibTeX
Vladlen Koltun, Micha Sharir:
Curve-Sensitive Cuttings. 863-878
Electronic Edition (link) BibTeX
Timothy M. Chan:
Low-Dimensional Linear Programming with Violations. 879-893
Electronic Edition (link) BibTeX
Richard Cole, Ramesh Hariharan:
Dynamic LCA Queries on Trees. 894-923
Electronic Edition (link) BibTeX
Yi-Ting Chiang, Ching-Chi Lin, Hsueh-I Lu:
Orderly Spanning Trees with Applications. 924-945
Electronic Edition (link) BibTeX
Anna Gál, Adi Rosén:
Omega(log n) Lower Bounds on the Amount of Randomness in 2-Private Computation. 946-959
Electronic Edition (link) BibTeX
Michael Kaminski:
A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields. 960-992
Electronic Edition (link) BibTeX
Grzegorz Malewicz:
A Work-Optimal Deterministic Algorithm for the Certified Write-All Problem with a Nontrivial Number of Asynchronous Processors. 993-1024
Electronic Edition (link) BibTeX

Volume 34, Number 5, 2005

Géraud Sénizergues:
The Bisimulation Problem for Equational Graphs of Finite Out-Degree. 1025-1106
Electronic Edition (link) BibTeX
Jeffrey C. Jackson, Rocco A. Servedio:
Learning Random Log-Depth Decision Trees under Uniform Distribution. 1107-1128
Electronic Edition (link) BibTeX
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev:
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. 1129-1146
Electronic Edition (link) BibTeX
Eldar Fischer:
The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance. 1147-1158
Electronic Edition (link) BibTeX
Kousha Etessami, Thomas Wilke, Rebecca A. Schuller:
Fair Simulation Relations, Parity Games, and State Space Reduction for Bu"chi Automata. 1159-1175
Electronic Edition (link) BibTeX
Arfst Nickelsen, Till Tantau:
The Complexity of Finding Paths in Graphs with Bounded Independence Number. 1176-1195
Electronic Edition (link) BibTeX
Amos Beimel, Enav Weinreb:
Separating the Power of Monotone Span Programs over Different Fields. 1196-1215
Electronic Edition (link) BibTeX
Panagiota Fatourou, Marios Mavronicolas, Paul G. Spirakis:
Efficiency of Oblivious versus Nonoblivious Schedulers for Optimistic, Rate-based Flow Control. 1216-1252
Electronic Edition (link) BibTeX
Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro:
Optimal Two-Stage Algorithms for Group Testing Problems. 1253-1270
Electronic Edition (link) BibTeX
Frank Kwang-Ming Hwang, Yong He, Yang Wang:
Strictly Nonblocking Multirate log_d(N, m, p) Networks. 1271-1278
Electronic Edition (link) BibTeX

Volume 34, Number 6, 2005

Mark McCann, Nicholas Pippenger:
SRT Division Algorithms as Dynamical Systems. 1279-1301
Electronic Edition (link) BibTeX
Thomas Erlebach, Klaus Jansen, Eike Seidel:
Polynomial-Time Approximation Schemes for Geometric Intersection Graphs. 1302-1323
Electronic Edition (link) BibTeX
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf:
Quantum Algorithms for Element Distinctness. 1324-1330
Electronic Edition (link) BibTeX
Esther Ezra, Micha Sharir:
Output-Sensitive Construction of the Union of Triangles. 1331-1351
Electronic Edition (link) BibTeX
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries. 1352-1369
Electronic Edition (link) BibTeX
Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan:
Approximating the Minimum Spanning Tree Weight in Sublinear Time. 1370-1379
Electronic Edition (link) BibTeX
John Hershberger, Subhash Suri, Csaba D. Tóth:
Binary Space Partitions of Orthogonal Subdivisions. 1380-1397
Electronic Edition (link) BibTeX
Seth Pettie, Vijaya Ramachandran:
A Shortest Path Algorithm for Real-Weighted Undirected Graphs. 1398-1431
Electronic Edition (link) BibTeX
Qi Cheng:
On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields. 1432-1442
Electronic Edition (link) BibTeX
David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter:
Duality Between Prefetching and Queued Writing with Parallel Disks. 1443-1463
Electronic Edition (link) BibTeX
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier:
Decidable and Undecidable Problems about Quantum Automata. 1464-1473
Electronic Edition (link) BibTeX
Qingmin Shi, Joseph JáJá:
Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry. 1474-1492
Electronic Edition (link) BibTeX
Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanés, Robert T. Schweller:
Complexities for Generalized Models of Self-Assembly. 1493-1515
Electronic Edition (link) BibTeX
Reuven Cohen, David Peleg:
Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems. 1516-1528
Electronic Edition (link) BibTeX