Theory Seminar: Hardness amplification proofs require majority

Ronen Shaltiel (Haifa University)

Sunday, 07.12.2008, 12:00

Taub 601

A function $f$ is $\delta$-hard for some class of circuits if every
circuit in the class errs on a $\delta$-fraction of the inputs. For
various classes of constant depth small size circuits there are explicit
functions that are $\delta$-hard for ``small'' values of $\delta$.
For stronger circuit classes there are many ``hardness amplification
theorems'' that show how to transform any $\delta$-hard function $f$
into a ``harder'' function $g$ that is $(1/2-\epsilon)$-hard (for very
small $\epsilon$). These theorems are proved using black-box reductions
that transform a circuit that computes $g$ correctly on a $1/2+\eps$
fraction of the inputs into a circuit that computes $f$ correctly on a
$1-\delta$-fraction of the inputs.

We show that such reductions cannot have low complexity: 1. Any such reduction ``can be used'' to compute the majority function on $1/\epsilon$ bits. 2. Any such reduction must make $\Omega(\log(1/\delta)/\eps2)$ oracle queries.

By the Natural Proofs paradigm of Razborov and Rudich (coupled with a cryptographic construction of Naor and Reingold) ``current techniques'' cannot prove lower bounds against circuit classes that can compute the majority function. Loosely speaking this means that: ``current techniques can only amplify hardness that we don't have''. The main difficulty in the proofs is that reductions that come up in proofs of hardness amplification theorems are allowed to be "nonuniform'' and we develop techniques to bound such reductions.

The talk will be self contained and I will give a brief survey of the area. Joint work with Emanuele Viola.

We show that such reductions cannot have low complexity: 1. Any such reduction ``can be used'' to compute the majority function on $1/\epsilon$ bits. 2. Any such reduction must make $\Omega(\log(1/\delta)/\eps2)$ oracle queries.

By the Natural Proofs paradigm of Razborov and Rudich (coupled with a cryptographic construction of Naor and Reingold) ``current techniques'' cannot prove lower bounds against circuit classes that can compute the majority function. Loosely speaking this means that: ``current techniques can only amplify hardness that we don't have''. The main difficulty in the proofs is that reductions that come up in proofs of hardness amplification theorems are allowed to be "nonuniform'' and we develop techniques to bound such reductions.

The talk will be self contained and I will give a brief survey of the area. Joint work with Emanuele Viola.