default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJournal 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 S. 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 S. 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 S. Vempala:
Fast monte-carlo algorithms for finding low-rank approximations. 1025-1041
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-05 22:38 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
