Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 51 Issue 2, March 2004

Resolution lower bounds for the weak pigeonhole principle
Ran Raz
Pages: 115-138
DOI: 10.1145/972639.972640
We prove that any Resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω(2nε), (for some global constant ε > 0). One corollary is that a...

Lenses in arrangements of pseudo-circles and their applications
Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky
Pages: 139-186
DOI: 10.1145/972639.972641
A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty...

The security of all RSA and discrete log bits
Johan Håstad, Mats Nåslund
Pages: 187-230
DOI: 10.1145/972639.972642
We study the security of individual bits in an RSA encrypted message EN(x). We show that given EN(x), predicting any single bit in x with only a nonnegligible advantage over the...

Number-theoretic constructions of efficient pseudo-random functions
Moni Naor, Omer Reingold
Pages: 231-262
DOI: 10.1145/972639.972643
We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction...

Segmentation problems
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
Pages: 263-280
DOI: 10.1145/972639.972644
We study a novel genre of optimization problems, which we call segmentation problems, motivated in part by certain aspects of clustering and data mining. For any classical optimization problem, the corresponding segmentation problem seeks to...

On sufficient conditions for unsatisfiability of random formulas
Albert Atserias
Pages: 281-311
DOI: 10.1145/972639.972645
A descriptive complexity approach to random 3-SAT is initiated. We show that unsatisfiability of any significant fraction of random 3-CNF formulas cannot be certified by any property that is expressible in Datalog. Combined with the known...

Existential second-order logic over graphs: Charting the tractability frontier
Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick
Pages: 312-362
DOI: 10.1145/972639.972646
Fagin's theorem, the first important result of descriptive complexity, asserts that a property of graphs is in NP if and only if it is definable by an existential second-order formula. In this article, we study the complexity of evaluating...