Journal of the ACM, Volume 48, 2001

Volume 48, Number 1, January 2001

• Timothy M. Chan:
  Dynamic planar convex hull operations in near-logarithmaic amortized time. 1-12
  
• Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
  Adversarial queuing theory. 13-38
  
• Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Frank Thomson Leighton, Zhiyong Liu, Jon M. Kleinberg:
  Universal-stability results and performance bounds for greedy contention-resolution protocols. 39-69
  
• David A. Basin, Harald Ganzinger:
  Automated complexity analysis based on ordered resolution. 70-109
  
• John Case, Dayanand S. Rajan, Anil M. Shende:
  Lattice computers for approximating Euclidean space. 110-144
  
• Jörg H. Siekmann, Graham Wrightson:
  Erratum: a counterexample to W. Bibel's and E. Eder's strong completeness result for connection graph resolution. 145-147
  

Volume 48, Number 2, March 2001

• Eli Ben-Sasson, Avi Wigderson:
  Short proofs are narrow - resolution made simple. 149-169
  
• Salvador Roura:
  Improved master theorems for divide-and-conquer recurrences. 170-205
  
• Martin Skutella:
  Convex quadratic and semidefinite programming relaxations in scheduling. 206-242
  
• Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott:
  On-line analysis of the TCP acknowledgment delay problem. 243-273
  
• Kamal Jain, Vijay V. Vazirani:
  Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation. 274-296
  
• Ka Wong Chong, Yijie Han, Tak Wah Lam:
  Concurrent threads and optimal parallel minimum spanning trees algorithm. 297-323
  
• Andrei Z. Broder, Alan M. Frieze, Eli Upfal:
  A general approach to dynamic packet routing with bounded buffers. 324-349
  

Volume 48, Number 3, May 2001

• Dominic Mayers:
  Unconditional security in quantum cryptography. 351-406
  
• Giovanni Manzini:
  An analysis of the Burrows-Wheeler transform. 407-430
  
• Georg Gottlob, Nicola Leone, Francesco Scarcello:
  The complexity of acyclic conjunctive queries. 431-498
  
• Rida A. Bazzi, Gil Neiger:
  Simplifying fault-tolerance: providing the abstraction of crash failures. 499-554
  
• Rowan Davies, Frank Pfenning:
  A modal analysis of staged computation. 555-604
  

Volume 48, Number 4, July 2001

• Adnan Darwiche:
  Decomposable negation normal form. 608-647
  
• Nir Friedman, Joseph Y. Halpern:
  Plausibility measures and default reasoning. 648-685
  
• Dorit S. Hochbaum:
  An efficient algorithm for image segmentation, Markov random fields and related problems. 686-701
  
• Dan Boneh, Matthew K. Franklin:
  Efficient generation of shared RSA keys. 702-722
  
• Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup:
  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. 723-760
  
• Satoru Iwata, Lisa Fleischer, Satoru Fujishige:
  A combinatorial strongly polynomial algorithm for minimizing submodular functions. 761-777
  
• Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf:
  Quantum lower bounds by polynomials. 778-797
  
• Johan Håstad:
  Some optimal inapproximability results. 798-859
  
• Luca Trevisan:
  Extractors and pseudorandom generators. 860-879
  
• Lauri Hella, Leonid Libkin, Juha Nurmonen, Limsoon Wong:
  Logics with aggregate operators. 880-907
  

Volume 48, Number 5, September 2001

• Carlo Meghini, Fabrizio Sebastiani, Umberto Straccia:
  A model of multimedia information retrieval. 909-970
  
• Alon Y. Halevy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli:
  Static analysis in datalog extensions. 971-1012
  
• Hagit Attiya, Eyal Dagan:
  Improved implementations of binary universal operations. 1013-1037
  
• Timothy J. Hickey, Qun Ju, Maarten H. van Emden:
  Interval arithmetic: From principles to implementation. 1038-1068
  
• Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber:
  A unified approach to approximating resource allocation and scheduling. 1069-1090
  

Volume 48, Number 6, November 2001

• Paolo Liberatore:
  Monotonic reductions, representative equivalence, and compilation of intractable problems. 1091-1125
  
• Jean B. Lasserre, Eduardo S. Zeron:
  A Laplace transform algorithm for the volume of a convex polytope. 1126-1140
  
• Avigdor Gal, Jonathan Eckstein:
  Managing periodically updated data in relational databases: a stochastic modeling approach. 1141-1183
  
• Markus Frick, Martin Grohe:
  Deciding first-order properties of locally tree-decomposable structures. 1184-1206
  
• Jan A. Bergstra, Alban Ponse:
  Register-machine based processes. 1207-1241