2008.08.26 | Peter Bro Miltersen

Michal Koucky, Czech Academy of Sciences, Seminar.

Title: Amplifying Lower Bounds by Means of Self-Reducibility

Abstract:

We observe that many important computational problems in $NC1$ share a simple self-reducibility property. We then show that, for any problem $A$ having this self-reducibility property, $A$ has polynomial size $TC0$ circuits if and only if it has $TC0$ circuits of size $n^{1+\\epsilon}$ for every $\\epsilon > 0$ (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, considerthe Boolean Formula Evaluation problem (BFE), which is complete for $NC1$ and has the self-reducibility property. Itfollows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth $d$ $TC0$ circuits of size $n^{1+\\epsilon_d}$. If one were able to improve this lower bound to show that there is some constant $\\epsilon>0$ suchthat every $TC0$ circuit family recognizing BFE has size $n^{1+\\epsilon}$, then it would follow that $TC0 \
eq NC1$. We show that proving lower bounds of the form $n^{1+\\epsilon}$ is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as $ACC0$, $TC0$ and $NC1$ via existing ``natural'' approaches to proving circuit lower bounds.

We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use ofknown time-space tradeoff lower bounds to show that SAT requires uniform depth $d$ $TC0$ and $AC0[6]$ circuits of size $n^{1+c}$ for some constant $c$ depending on $d$.

Joint work with Eric Allender