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

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
  
• Markus Bläser:
  A Complete Characterization of the Algebras of Minimal Bilinear Complexity. 277-298
  
• Benjamin Doerr:
  Nonindependent Randomized Rounding and an Application to Digital Halftoning. 299-317
  
• Rajat Bhattacharjee, Ashish Goel, Zvi Lotker:
  Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. 318-332
  
• 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
  
• Gruia Calinescu, Howard J. Karloff, Yuval Rabani:
  Approximation Algorithms for the 0-Extension Problem. 358-372
  
• Kai-min Chung, Hsueh-I Lu:
  An Optimal Algorithm for the Maximum-Density Segment Problem. 373-387
  
• Satish Rao, Andréa W. Richa:
  New Approximation Techniques for Some Linear Ordering Problems. 388-404
  
• Mikkel Thorup:
  Quick k-Median, k-Center, and Facility Location for Sparse Graphs. 405-432
  
• S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke:
  Online Scheduling to Minimize Average Stretch. 433-452
  
• Anupam Gupta, Amit Kumar, Rajeev Rastogi:
  Traveling with a Pez Dispenser (or, Routing Issues in MPLS). 453-474
  
• Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler:
  The Simplex Algorithm in Dimension Three. 475-497
  
• Yasunori Ishihara, Shin Ishii, Hiroyuki Seki, Minoru Ito:
  Temporal Reasoning about Two Concurrent Sequences of Events. 498-513
  

Volume 34, Number 3, 2005

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

Volume 34, Number 4, 2005

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

Volume 34, Number 5, 2005

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

Volume 34, Number 6, 2005

• Mark McCann, Nicholas Pippenger:
  SRT Division Algorithms as Dynamical Systems. 1279-1301
  
• Thomas Erlebach, Klaus Jansen, Eike Seidel:
  Polynomial-Time Approximation Schemes for Geometric Intersection Graphs. 1302-1323
  
• 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
  
• Esther Ezra, Micha Sharir:
  Output-Sensitive Construction of the Union of Triangles. 1331-1351
  
• Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
  Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries. 1352-1369
  
• Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan:
  Approximating the Minimum Spanning Tree Weight in Sublinear Time. 1370-1379
  
• John Hershberger, Subhash Suri, Csaba D. Tóth:
  Binary Space Partitions of Orthogonal Subdivisions. 1380-1397
  
• Seth Pettie, Vijaya Ramachandran:
  A Shortest Path Algorithm for Real-Weighted Undirected Graphs. 1398-1431
  
• Qi Cheng:
  On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields. 1432-1442
  
• David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter:
  Duality Between Prefetching and Queued Writing with Parallel Disks. 1443-1463
  
• Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier:
  Decidable and Undecidable Problems about Quantum Automata. 1464-1473
  
• Qingmin Shi, Joseph JáJá:
  Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry. 1474-1492
  
• 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
  
• Reuven Cohen, David Peleg:
  Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems. 1516-1528