Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

DOI10.4230/LIPICS.CCC.2016.33MaRDI QIDQ5368767zbMATH OpenOpenAlexFDO

Authors Mrinal Kumar, Ramprasad Saptharishi, Michael A. Forbes

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1605.04207

zbMATH Keywords

lower boundsarithmetic circuitsBoolean circuitsfunctional computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P$ if for every $xin{0,1}^n$ we have that $C(x)=P(x)$. This is in contrast to syntactically computing $P$, when $CequivP$ 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 $$ 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 [KS15] 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.

Recommendations

• scientific article; zbMATH DE number 4170847
• scientific article; zbMATH DE number 806753
• Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
• Lower bounds for the complexity of restrictions of Boolean functions
• Elusive functions and lower bounds for arithmetic circuits
• Circuit lower bounds in bounded arithmetics
• A Selection of Lower Bounds for Arithmetic Circuits
• scientific article; zbMATH DE number 850402
• scientific article; zbMATH DE number 15477
• Lower bounds on arithmetic circuits via partial derivatives

Cited in

(7)

• scientific article; zbMATH DE number 7204375 (Why is no real title available?)
• On the Symmetries of and Equivalence Test for Design Polynomials.
• Lower bounds on the area complexity of Boolean circuits
• On Lower Bounds for Constant Width Arithmetic Circuits
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• scientific article; zbMATH DE number 6007880 (Why is no real title available?)
• Succinct functional commitment for a large class of arithmetic circuits

This page was built for publication: Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368767)