Journal of the ACM, Volume 51, 2004

Volume 51, Number 1, January 2004

• Phokion G. Kolaitis, Victor Vianu:
  Foreword. 1
  
• Gerome Miklau, Dan Suciu:
  Containment and equivalence for a fragment of XPath. 2-45
  
• Chung-Min Chen, Christine T. Cheng:
  From discrepancy to declustering: Near-optimal multidimensional declustering strategies for range queries. 46-73
  
• Georg Gottlob, Christoph Koch:
  Monadic datalog and the expressive power of languages for Web information extraction. 74-113
  

Volume 51, Number 2, March 2004

• Ran Raz:
  Resolution lower bounds for the weak pigeonhole principle. 115-138
  
• Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky:
  Lenses in arrangements of pseudo-circles and their applications. 139-186
  
• Johan Håstad, Mats Näslund:
  The security of all RSA and discrete log bits. 187-230
  
• Moni Naor, Omer Reingold:
  Number-theoretic constructions of efficient pseudo-random functions. 231-262
  
• Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
  Segmentation problems. 263-280
  
• Albert Atserias:
  On sufficient conditions for unsatisfiability of random formulas. 281-311
  
• Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick:
  Existential second-order logic over graphs: Charting the tractability frontier. 312-362
  

Volume 51, Number 3, May 2004

• Jochen Alber, Michael R. Fellows, Rolf Niedermeier:
  Polynomial-time data reduction for dominating set. 363-384
  
• Daniel A. Spielman, Shang-Hua Teng:
  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. 385-463
  
• Peter Bürgisser, Martin Lotz:
  Lower bounds on the bounded coefficient complexity of bilinear maps. 464-482
  
• Wojciech Plandowski:
  Satisfiability of word equations with constants is in PSPACE. 483-496
  
• Ravi Kannan, Santosh Vempala, Adrian Vetta:
  On clusterings: Good, bad and spectral. 497-515
  

Volume 51, Number 4, July 2004

• Luca Becchetti, Stefano Leonardi:
  Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. 517-539
  
• Dimitris Bertsimas, Santosh Vempala:
  Solving convex programs by random walks. 540-556
  
• Ran Canetti, Oded Goldreich, Shai Halevi:
  The random oracle methodology, revisited. 557-594
  
• Scott Aaronson, Yaoyun Shi:
  Quantum lower bounds for the collision and the element distinctness problems. 595-605
  
• Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan:
  Approximating extent measures of points. 606-635
  
• Jan M. Hochstein, Karsten Weihe:
  Edge-disjoint routing in plane switch graphs in linear time. 636-670
  
• Mark Jerrum, Alistair Sinclair, Eric Vigoda:
  A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. 671-697
  

Volume 51, Number 5, September 2004

• Vladlen Koltun:
  Almost tight upper bounds for vertical decompositions in four dimensions. 699-730
  
• Valter Crescenzi, Giansalvatore Mecca:
  Automatic information extraction from large websites. 731-779
  
• Shlomi Dolev, Jennifer L. Welch:
  Self-stabilizing clock synchronization in the presence of Byzantine faults. 780-799
  
• Robert C. Steinke, Gary J. Nutt:
  A unified theory of shared memory consistency. 800-849
  

Volume 51, Number 6, November 2004

• Cynthia Dwork, Moni Naor, Amit Sahai:
  Concurrent zero-knowledge. 851-898
  
• Oded Regev:
  New lattice-based cryptographic constructions. 899-942
  
• David Kempe, Jon M. Kleinberg, Alan J. Demers:
  Spatial gossip and resource location protocols. 943-967
  
• Camil Demetrescu, Giuseppe F. Italiano:
  A new approach to dynamic all pairs shortest paths. 968-992
  
• Mikkel Thorup:
  Compact oracles for reachability and approximate distances in planar digraphs. 993-1024
  
• Alan M. Frieze, Ravi Kannan, Santosh Vempala:
  Fast monte-carlo algorithms for finding low-rank approximations. 1025-1041
  

Last update Sat May 25 20:37:30 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page