enter search term and/or author name
Resolution lower bounds for the weak pigeonhole principle
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
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
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
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...
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
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
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
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...