The Taub Faculty of Computer Science Events and Talks

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.