Paper Info
Title
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity.
Abstract
We say that a circuit C over a field F functionally computes a polynomial P ∈ F[x1, x2, ..., xn] if for every x ∈ {0, 1}n we have that C(x) = P(x). This is in contrast to syntactically computing P, when C ≡ 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: Exponential lower bounds for homogeneous depth-3 arithmetic circuits for a polynomial in VNP. 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 ACC0. 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 [9] that over constant sized finite fields, strong enough average case functional lower bounds for homogeneous depth-4 circuits imply superpolynomial 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.
Year
DOI
Venue
2016
10.4230/LIPIcs.CCC.2016.33
Electronic Colloquium on Computational Complexity (ECCC)
Keywords
DocType
Volume
boolean circuits,arithmetic circuits,lower bounds,functional computation
Journal
23
ISSN
Citations 
PageRank 
1868-8969
3
0.37
References 
Authors
11
3
Name
Order
Citations
PageRank
Michael A. Forbes130.37
Mrinal Kumar 00012649.94
Ramprasad Saptharishi318413.72