Journal of the ACM, Volume 52, 2005

Volume 52, Number 1, January 2005

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

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
  
• Nir Ailon, Bernard Chazelle:
  Lower bounds for linear degeneracy testing. 157-171
  
• Ronen Shaltiel, Christopher Umans:
  Simple extractors for all min-entropies and a new pseudorandom generator. 172-216
  
• Micah Adler:
  Trade-offs in probabilistic packet marking for IP traceback. 217-244
  
• Tova Milo, Victor Vianu:
  Introduction. 245
  
• Marcelo Arenas, Leonid Libkin:
  An information-theoretic approach to normal forms for relational and XML data. 246-283
  
• Georg Gottlob, Christoph Koch, Reinhard Pichler, Luc Segoufin:
  The complexity of XPath query evaluation and XML typing. 284-335
  

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
  
• David Detlefs, Greg Nelson, James B. Saxe:
  Simplify: a theorem prover for program checking. 365-473
  
• Ninghui Li, John C. Mitchell, William H. Winsborough:
  Beyond proof-of-compliance: security analysis in trust management. 474-514
  

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
  
• 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
  
• Paolo Ferragina, Giovanni Manzini:
  Indexing compressed text. 552-581
  
• Matthew Andrews, Antonio Fernández, Ashish Goel, Lisa Zhang:
  Source routing and scheduling in packet networks. 582-601
  
• Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko:
  Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. 602-626
  
• John Tang Boyland:
  Remote attribute grammars. 627-687
  
• Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini, Marinella Sciortino:
  Boosting textual compression in optimal linear time. 688-713
  

Volume 52, Number 5, September 2005

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

Volume 52, Number 6, November 2005

• Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas:
  Time-space lower bounds for satisfiability. 835-865
  
• 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
  
• Anindya Banerjee, David A. Naumann:
  Ownership confinement ensures representation independence for object-oriented programs. 894-960
  
• Massimo Merro, Francesco Zappa Nardelli:
  Behavioral theory for mobile ambients. 961-1023
  

Last update Fri May 17 20:22:44 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page