## Reimer's inequality and Rudich's conjecture

- Nov. 9, 2001
- 3:30 p.m.
- LeConte 312

## Abstract

We prove Rudich's conjecture, a long-outstanding problem in combinatorial probability arising from Rudich's work on reducibility among cryptographic primitives. Roughly the conjecture states that if a family of subcubes of the discrete cube is a near partition, then there is a significant dependence among the family. (The subcubes are viewed as events where a point is selected from the cube according to a product distribution.)

To prove this we discover and use a correlation inequality that is in some sense "dual" to Reimer's inequality (the celebrated inequality conjectured by van den Berg and Kesten).

We also use this inequality to prove an upper bound on the approximate decision tree complexity of a boolean function that is quadratic in its approximate certificate complexity (just as in the exact case.)