Journal of the ACM, Volume 51, 2004

Volume 51, Number 1, January 2004

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

Ran Raz:
Resolution lower bounds for the weak pigeonhole principle. 115-138
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX
Johan Håstad, Mats Näslund:
The security of all RSA and discrete log bits. 187-230
Electronic Edition (ACM DL) BibTeX
Moni Naor, Omer Reingold:
Number-theoretic constructions of efficient pseudo-random functions. 231-262
Electronic Edition (ACM DL) BibTeX
Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan:
Segmentation problems. 263-280
Electronic Edition (ACM DL) BibTeX
Albert Atserias:
On sufficient conditions for unsatisfiability of random formulas. 281-311
Electronic Edition (ACM DL) BibTeX
Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick:
Existential second-order logic over graphs: Charting the tractability frontier. 312-362
Electronic Edition (ACM DL) BibTeX

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

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

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

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