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
  Electronic Edition (link) BibTeX
• 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
  Electronic Edition (link) BibTeX
• Dieter van Melkebeek, Rahul Santhanam:
  Holographic Proofs and Derandmization. 59-90
  Electronic Edition (link) BibTeX
• 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
  Electronic Edition (link) BibTeX
• Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel:
  Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. 110-119
  Electronic Edition (link) BibTeX
• Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, David Peleg:
  Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds. 120-131
  Electronic Edition (link) BibTeX
• Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
  The Complexity of Approximating the Entropy. 132-150
  Electronic Edition (link) BibTeX
• Jie Gao, Li Zhang:
  Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications. 151-169
  Electronic Edition (link) BibTeX
• Greg Kuperberg:
  A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. 170-188
  Electronic Edition (link) BibTeX
• Refael Hassin, Asaf Levin:
  A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem. 189-200
  Electronic Edition (link) BibTeX
• 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
  Electronic Edition (link) BibTeX
• Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan:
  Bounds on the Efficiency of Generic Cryptographic Constructions. 217-246
  Electronic Edition (link) BibTeX
• Guy Kortsarz, Zeev Nutov:
  Approximating k-node Connected Subgraphs via Critical Graphs. 247-257
  Electronic Edition (link) BibTeX

Volume 35, Number 2, 2005

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

Volume 35, Number 3, 2005

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

Volume 35, Number 4, 2006

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

Volume 35, Number 5, 2006

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

Volume 35, Number 6, 2006

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