Resolution lower bounds for the weak pigeonhole principle.
Segmentation problems.
Lenses in arrangements of pseudo-circles and their applications.
The security of all RSA and discrete log bits.
Existential second-order logic over graphs: Charting the tractability frontier.
On sufficient conditions for unsatisfiability of random formulas.
Number-theoretic constructions of efficient pseudo-random functions.