2002 · 44 citations · 6 references
ComputingComputer ScienceMathematicsCombinatoricsCryptographyTheory Of ComputationCryptographic ComplexityRandomized ComplexityOne-way FunctionsOracle ComputationOracle InterpretationOracle PropertyRandom Oracle Model
We prove a dual version of the celebrated inequality of D. Reimer (a.k.a. the van den Berg-Kesten conjecture). We use the dual inequality to prove a combinatorial conjecture of S. Rudich motivated by questions in cryptographic complexity. One consequence of Rudich's Conjecture is that there is an oracle relative to which one-way functions exist but one-way permutations do not. The dual inequality has another combinatorial consequence which allows R. Impagliazzo and S. Rudich to prove that if P=NP then NP/spl cap/coNP/spl sube/i.o.AvgP relative to a random oracle.
6