Journal of the ACM, Volume 52, 2005

Volume 52, Number 1, January 2005

• Mikkel Thorup, Uri Zwick:
  Approximate distance oracles. 1-24
  Electronic Edition (ACM DL) BibTeX
• Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack:
  Determining approximate shortest paths on weighted polyhedral surfaces. 25-53
  Electronic Edition (ACM DL) BibTeX
• Robert B. Ross, V. S. Subrahmanian, John Grant:
  Aggregate operators in probabilistic databases. 54-101
  Electronic Edition (ACM DL) BibTeX
• Martín Abadi, Bruno Blanchet:
  Analyzing security protocols with secrecy types and logic programs. 102-146
  Electronic Edition (ACM DL) BibTeX

Volume 52, Number 2, March 2005

• Camil Demetrescu, Giuseppe F. Italiano:
  Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O(n² barrier. 147-156
  Electronic Edition (ACM DL) BibTeX
• Nir Ailon, Bernard Chazelle:
  Lower bounds for linear degeneracy testing. 157-171
  Electronic Edition (ACM DL) BibTeX
• Ronen Shaltiel, Christopher Umans:
  Simple extractors for all min-entropies and a new pseudorandom generator. 172-216
  Electronic Edition (ACM DL) BibTeX
• Micah Adler:
  Trade-offs in probabilistic packet marking for IP traceback. 217-244
  Electronic Edition (ACM DL) BibTeX
• Tova Milo, Victor Vianu:
  Introduction. 245
  Electronic Edition (ACM DL) BibTeX
• Marcelo Arenas, Leonid Libkin:
  An information-theoretic approach to normal forms for relational and XML data. 246-283
  Electronic Edition (ACM DL) BibTeX
• Georg Gottlob, Christoph Koch, Reinhard Pichler, Luc Segoufin:
  The complexity of XPath query evaluation and XML typing. 284-335
  Electronic Edition (ACM DL) BibTeX

Volume 52, Number 3, May 2005

• Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
  An improved exponential-time algorithm for k-SAT. 337-364
  Electronic Edition (ACM DL) BibTeX
• David Detlefs, Greg Nelson, James B. Saxe:
  Simplify: a theorem prover for program checking. 365-473
  Electronic Edition (ACM DL) BibTeX
• Ninghui Li, John C. Mitchell, William H. Winsborough:
  Beyond proof-of-compliance: security analysis in trust management. 474-514
  Electronic Edition (ACM DL) BibTeX

Volume 52, Number 4, July 2005

• Gianni Franceschini, Viliam Geffert:
  An in-place sorting with O(nlog n) comparisons and O(n) moves. 515-537
  Electronic Edition (ACM DL) BibTeX
• Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor:
  Asymmetric k-center is log^* n-hard to approximate. 538-551
  Electronic Edition (ACM DL) BibTeX
• Paolo Ferragina, Giovanni Manzini:
  Indexing compressed text. 552-581
  Electronic Edition (ACM DL) BibTeX
• Matthew Andrews, Antonio Fernández, Ashish Goel, Lisa Zhang:
  Source routing and scheduling in packet networks. 582-601
  Electronic Edition (ACM DL) BibTeX
• Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko:
  Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. 602-626
  Electronic Edition (ACM DL) BibTeX
• John Tang Boyland:
  Remote attribute grammars. 627-687
  Electronic Edition (ACM DL) BibTeX
• Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini, Marinella Sciortino:
  Boosting textual compression in optimal linear time. 688-713
  Electronic Edition (ACM DL) BibTeX

Volume 52, Number 5, September 2005

• Richard E. Korf, Weixiong Zhang, Ignacio Thayer, Heath Hohwald:
  Frontier search. 715-748
  Electronic Edition (ACM DL) BibTeX
• Dorit Aharonov, Oded Regev:
  Lattice problems in NP cap coNP. 749-765
  Electronic Edition (ACM DL) BibTeX
• Bo Brinkman, Moses Charikar:
  On the impossibility of dimension reduction in l₁. 766-788
  Electronic Edition (ACM DL) BibTeX
• Subhash Khot:
  Hardness of approximating the shortest vector problem in lattices. 789-808
  Electronic Edition (ACM DL) BibTeX
• Matthew Andrews, Lisa Zhang:
  Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data. 809-834
  Electronic Edition (ACM DL) BibTeX

Volume 52, Number 6, November 2005

• Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas:
  Time-space lower bounds for satisfiability. 835-865
  Electronic Edition (ACM DL) BibTeX
• Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
  Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. 866-893
  Electronic Edition (ACM DL) BibTeX
• Anindya Banerjee, David A. Naumann:
  Ownership confinement ensures representation independence for object-oriented programs. 894-960
  Electronic Edition (ACM DL) BibTeX
• Massimo Merro, Francesco Zappa Nardelli:
  Behavioral theory for mobile ambients. 961-1023
  Electronic Edition (ACM DL) BibTeX