Journal of the ACM, Volume 53, 2006

Volume 53, Number 1, January 2006

• János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber:
  On the Sum-of-Squares algorithm for bin packing. 1-65
  
• Andrei A. Bulatov:
  A dichotomy theorem for constraint satisfaction problems on a 3-element set. 66-120
  
• Mark Scharbrodt, Thomas Schickinger, Angelika Steger:
  A new average case analysis for completion time scheduling. 121-146
  
• Philippe Flajolet, Wojciech Szpankowski, Brigitte Vallée:
  Hidden word statistics. 147-183
  
• Ashwin Nayak, Julia Salzman:
  Limits on the ability of quantum states to convey classical messages. 184-206
  

Volume 53, Number 2, March 2006

• Dan Suciu, Victor Vianu:
  Introduction. 207
  
• Albert Atserias, Anuj Dawar, Phokion G. Kolaitis:
  On preservation under homomorphisms and unions of conjunctive queries. 208-237
  
• Georg Gottlob, Christoph Koch, Klaus U. Schulz:
  Conjunctive queries over trees. 238-272
  
• Michael Benedikt, Bart Kuijpers, Christof Löding, Jan Van den Bussche, Thomas Wilke:
  A characterization of first-order topological properties of planar spatial data. 273-305
  

Volume 53, Number 3, May 2006

• Piotr Indyk:
  Stable distributions, pseudorandom generators, embeddings, and data stream computation. 307-323
  
• Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan:
  Dependent rounding and its applications to approximation algorithms. 324-360
  
• Yih-En Andrew Ban, Herbert Edelsbrunner, Johannes Rudolph:
  Interface surfaces for protein-protein complexes. 361-378
  
• Ori Shalev, Nir Shavit:
  Split-ordered lists: Lock-free extensible hash tables. 379-405
  
• Mark-Jan Nederhof, Giorgio Satta:
  Probabilistic parsing strategies. 406-436
  
• René A. Sitters, Leen Stougie:
  The generalized two-server problem. 437-458
  
• Andrew M. Pitts:
  Alpha-structural recursion and induction. 459-506
  
• Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani:
  Computing with highly mixed states. 507-531
  

Volume 53, Number 4, July 2006

• Jinbo Xu, Bonnie Berger:
  Fast and accurate algorithms for protein side-chain packing. 533-557
  
• Oded Goldreich, Madhu Sudan:
  Locally testable codes and PCPs of almost-linear length. 558-655
  
• Jeffrey Scott Vitter, David A. Hutchinson:
  Distribution sort with randomized cycling. 656-680
  
• Amir M. Ben-Amram, Holger Petersen:
  Backing up in singly linked lists. 681-705
  

Volume 53, Number 5, September 2006

• Julia Chuzhoy, Joseph Naor:
  New hardness results for congestion minimization and machine scheduling. 707-721
  
• Benny Chor, Tamir Tuller:
  Finding a maximum likelihood tree is hard. 722-744
  
• Matthew Andrews, Lisa Zhang:
  Logarithmic hardness of the undirected edge-disjoint paths problem. 745-761
  
• Daniela Pucci de Farias, Nimrod Megiddo:
  Combining expert advice in reactive environments. 762-799
  
• Harold N. Gabow:
  Using expander graphs to find vertex connectivity. 800-844
  
• Avrim Blum, Tuomas Sandholm, Martin Zinkevich:
  Online algorithms for market clearing. 845-879
  

Volume 53, Number 6, November 2006

• Yehuda Lindell, Anna Lysyanskaya, Tal Rabin:
  On the composition of authenticated Byzantine Agreement. 881-917
  
• Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt:
  Linear work suffix array construction. 918-936
  
• Robert Nieuwenhuis, Albert Oliveras, Cesare Tinelli:
  Solving SAT and SAT Modulo Theories: From an abstract Davis--Putnam--Logemann--Loveland procedure to DPLL(T). 937-977
  
• David B. Shmoys, Chaitanya Swamy:
  An approximation scheme for stochastic linear programming and its application to stochastic integer programs. 978-1012