SIAM Journal on Computing, Volume 35

Volume 35, Number 1, 2005

• Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
  Some 3CNF Properties Are Hard to Test. 1-21
  
• Michael Lindenbaum, Hanan Samet, Gísli R. Hjaltason:
  A Probabilistic Analysis of Trie-Based Sorting of Large Collections of Line Segments in Spatial Databases. 22-58
  
• Dieter van Melkebeek, Rahul Santhanam:
  Holographic Proofs and Derandmization. 59-90
  
• Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler:
  Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. 91-109
  
• Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel:
  Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. 110-119
  
• Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, David Peleg:
  Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds. 120-131
  
• Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
  The Complexity of Approximating the Entropy. 132-150
  
• Jie Gao, Li Zhang:
  Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications. 151-169
  
• Greg Kuperberg:
  A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. 170-188
  
• Refael Hassin, Asaf Levin:
  A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem. 189-200
  
• Kazuyuki Amano, Akira Maruoka:
  A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates. 201-216
  
• Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan:
  Bounds on the Efficiency of Generic Cryptographic Constructions. 217-246
  
• Guy Kortsarz, Zeev Nutov:
  Approximating k-node Connected Subgraphs via Critical Graphs. 247-257
  

Volume 35, Number 2, 2005

• Petr Hlinený:
  A Parametrized Algorithm for Matroid Branch-Width. 259-277
  
• Susanne Albers, Markus Schmidt:
  On the Performance of Greedy Algorithms in Packet Buffering. 278-304
  
• Costas Busch, Srikanta Tirthapura:
  Analysis of Link Reversal Routing Algorithms. 305-326
  
• Ketan Dalal, Luc Devroye, Ebrahim Malalla, Erin McLeish:
  Two-Way Chaining with Reassignment. 327-340
  
• Michael A. Bender, Erik D. Demaine, Martin Farach-Colton:
  Cache-Oblivious B-Trees. 341-358
  
• Gyung-Ok Lee, Kwang-Moo Choe:
  A Powerful LL(k) Covering Transformation. 359-377
  
• Roberto Grossi, Jeffrey Scott Vitter:
  Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. 378-407
  
• Joel Friedman, Andreas Goerdt, Michael Krivelevich:
  Recognizing More Unsatisfiable Random k-SAT Instances Efficiently. 408-430
  
• Leah Epstein, Rob van Stee:
  Optimal Online Algorithms for Multidimensional Packing Problems. 431-448
  
• April Rasala Lehman, Gordon T. Wilfong:
  http: //epubs.siam.org/SICOMP/volume-35/art_43425.html. 449-485
  
• Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
  Strong Spatial Mixing with Fewer Colors for Lattice Graphs. 486-517
  

Volume 35, Number 3, 2005

• Klaus Jansen, Lorant Porkolab:
  General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time. 519-530
  
• Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia:
  Optimal Covering Tours with Turn Costs. 531-566
  
• Darin Goldstein, Kojiro Kobayashi:
  On the Complexity of Network Synchronization. 567-589
  
• Ernst-Erich Doberkat:
  Stochastic Relations: Congruences, Bisimulations and the Hennessy--Milner Theorem. 590-626
  
• Bernard Chazelle, Ding Liu, Avner Magen:
  Sublinear Geometric Algorithms. 627-646
  
• Bjørn Kjos-Hanssen, André Nies, Frank Stephan:
  Lowness for the Class of Schnorr Random Reals. 647-657
  
• Minming Li, F. Frances Yao:
  An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. 658-671
  
• Michael Elkin, Guy Kortsarz:
  A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. 672-689
  
• Dirk L. Vertigan:
  The Computational Complexity of Tutte Invariants for Planar Graphs. 690-712
  
• Chandra Chekuri, Sanjeev Khanna:
  A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. 713-728
  
• Weiping Shi, Chen Su:
  The Rectilinear Steiner Arborescence Problem Is NP-Complete. 729-740
  
• Meghanad D. Wagh, Osman Guzide:
  Mapping Cycles and Trees on Wrap-Around Butterfly Graphs. 741-765
  
• Hung Quang Ngo:
  WDM Switching Networks, Rearrangeable and Nonblocking [w, f]-connectors. 766-785
  

Volume 35, Number 4, 2006

• László Babai:
  Special Issue Dedicated To The Thirty-Sixth Annual ACM Symposium On Theory Of Computing (STOC 2004).
  
• Noga Alon, Assaf Naor:
  Approximating the Cut-Norm via Grothendieck's Inequality. 787-803
  
• Scott Aaronson:
  Lower Bounds for Local Search by Quantum Arguments. 804-824
  
• Daniel Bienstock, Garud Iyengar:
  Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations. 825-854
  
• René Beier, Berthold Vöcking:
  Typical Properties of Winners and Losers in Discrete Optimization. 855-881
  
• Jonathan A. Kelner:
  Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus. 882-902
  
• Alexander Healy, Salil P. Vadhan, Emanuele Viola:
  Using Nondeterminism to Amplify Hardness. 903-931
  
• Mihai Patrascu, Erik D. Demaine:
  Logarithmic Lower Bounds in the Cell-Probe Model. 932-963
  
• Uriel Feige:
  On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. 964-984
  
• László Lovász, Santosh Vempala:
  Hit-and-Run from a Corner. 985-1005
  

Volume 35, Number 5, 2006

• Amihood Amir, Yonatan Aumann, Moshe Lewenstein, Ely Porat:
  Function Matching. 1007-1022
  
• Sean Curran, Orlando Lee, Xingxing Yu:
  Finding Four Independent Trees . 1023-1058
  
• Holger Petersen, John Michael Robson:
  Efficient Simulations by Queue Machines. 1059-1069
  
• Julia Kempe, Alexei Kitaev, Oded Regev:
  The Complexity of the Local Hamiltonian Problem. 1070-1097
  
• Jesper Jansson, Nguyen Bao Nguyen, Wing-Kin Sung:
  Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. 1098-1121
  
• Karl-Heinz Niggl, Henning Wunderlich:
  Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs. 1122-1147
  
• Sariel Har-Peled, Manor Mendel:
  Fast Construction of Nets in Low-Dimensional Metrics and Their Applications. 1148-1184
  
• Omer Reingold, Ronen Shaltiel, Avi Wigderson:
  Extracting Randomness via Repeated Condensing. 1185-1209
  
• Markus Lohrey:
  Word Problems and Membership Problems on Compressed Words. 1210-1240
  
• Maurice Queyranne, Andreas S. Schulz:
  Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems. 1241-1253
  
• Moni Naor, Benny Pinkas:
  Oblivious Polynomial Evaluation. 1254-1281
  

Volume 35, Number 6, 2006

• Klaus Weihrauch, Ning Zhong:
  An Algorithm for Computing Fundamental Solutions. 1283-1294
  
• Serge Abiteboul, Stephen Alstrup, Haim Kaplan, Tova Milo, Theis Rauhe:
  Compact Labeling Scheme for Ancestor Queries. 1295-1309
  
• Christoph Dürr, Mark Heiligman, Peter Høyer, Mehdi Mhalla:
  Quantum Query Complexity of Some Graph Problems. 1310-1328
  
• Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
  The Approximability of Three-valued MAX CSP. 1329-1349
  
• Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking:
  Balanced Allocations: The Heavily Loaded Case. 1350-1385
  
• Floris Geerts, Bart Kuijpers, Jan Van den Bussche:
  Linearization and Completeness Results for Terminating Transitive Closure Queries on Spatial Databases. 1386-1439
  
• Hua-Huai Chern, Hsien-Kuei Hwang:
  Partial Match Queries in Random k-d Trees. 1440-1466
  
• Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
  Power from Random Strings. 1467-1493
  
• Christian Worm Mortensen:
  Fully Dynamic Orthogonal Range Reporting on RAM. 1494-1525