Revision #1 Authors: Alexander Golovnev, Alexander Kulikov

Accepted on: 13th December 2018 23:17

Downloads: 1

Keywords:

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for obtaining circuit lower bounds. Namely, we prove that every (unbounded-depth) circuit of size $s$ can be expressed as an OR of $2^{s/3.9}$ $16$-CNFs. While this structural result does not immediately lead to new lower bounds, it suggests a new avenue of attack on them.

Our result complements the classical depth reduction result of Valiant which asserts that logarithmic-depth circuits of linear size can be computed by an OR of $2^{\varepsilon n}$ $n^{\delta}$-CNFs. It is known that no such graph-theoretic reduction can work for circuits of super-logarithmic depth. We overcome this limitation (for small circuits) by taking into account both the graph-theoretic and functional properties of circuits.

We show that qualitative improvements of the following pseudorandom constructions imply qualitative (from $3n$ to $\omega(n)$) improvement of size lower bounds for log-depth circuits via Valiant's reduction: dispersers for varieties, correlation with constant degree polynomials, matrix rigidity, and hardness for depth-$3$ circuits with constant bottom fan-in. On the other hand, now even modest quantitative improvements of the known constructions give elementary proofs of quantitatively stronger circuit lower bounds ($3.9n$ instead of $3n$).

TR18-192 Authors: Alexander Golovnev, Alexander Kulikov

Publication: 12th November 2018 18:34

Downloads: 202

Keywords:

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for obtaining circuit lower bounds. Namely, we prove that every (unbounded-depth) circuit of size $s$ can be expressed as an OR of $2^{s/3.9}$ $16$-CNFs. While this structural result does not immediately lead to new lower bounds, it suggests a new avenue of attack on them.

Our result complements the classical depth reduction result of Valiant which asserts that logarithmic-depth circuits of linear size can be computed by an OR of $2^{\varepsilon n}$ $n^{\delta}$-CNFs. It is known that no such graph-theoretic reduction can work for circuits of super-logarithmic depth. We overcome this limitation (for small circuits) by taking into account both the graph-theoretic and functional properties of circuits.

We show that qualitative improvements of the following pseudorandom constructions imply qualitative (from $3n$ to $\omega(n)$) improvement of size lower bounds for log-depth circuits via Valiant's reduction: dispersers for varieties, correlation with constant degree polynomials, matrix rigidity, and hardness for depth-$3$ circuits with constant bottom fan-in. On the other hand, now even modest quantitative improvements of the known constructions give elementary proofs of quantitatively stronger circuit lower bounds ($3.9n$ instead of $3n$).