ECCC-Report TR16-045https://eccc.weizmann.ac.il/report/2016/045Comments and Revisions published for TR16-045en-usTue, 22 Mar 2016 13:45:58 +0200
Paper TR16-045
| Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity |
Mrinal Kumar,
Michael Forbes,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2016/045We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P \in F[x_1, x_2, \ldots, x_n]$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to {syntactically} computing $P$, when $C \equiv P$ as formal polynomials. In this paper, we study the question of proving lower bounds for homogeneous depth-$3$ and depth-$4$ arithmetic circuits for functional computation. We prove the following results :
1. Exponential lower bounds homogeneous depth-$3$ arithmetic circuits for a polynomial in $VNP$.
2. Exponential lower bounds for homogeneous depth-$4$ arithmetic circuits with bounded individual degree for a polynomial in $VNP$.
Our main motivation for this line of research comes from our observation that strong enough functional lower bounds for even very special depth-$4$ arithmetic circuits for the Permanent imply a separation between #P and ACC. Thus, improving the second result to get rid of the {bounded individual degree} condition could lead to substantial progress in boolean circuit complexity. Besides, it is known from a recent result of Kumar and Saptharishi [KumarSaptharishi15] that over constant sized finite fields, strong enough {average case} functional lower bounds for homogeneous depth-$4$ circuits imply super-polynomial lower bounds for homogeneous depth-$5$ circuits.
Our proofs are based on a family of new complexity measures called shifted evaluation dimension, and might be of independent interest. Tue, 22 Mar 2016 13:45:58 +0200https://eccc.weizmann.ac.il/report/2016/045