Volume 51, Number 1, January 2004
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
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
Volume 51, Number 6, November 2004
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