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

DOI10.4230/LIPICS.CCC.2016.33zbMATH Open1380.68194arXiv1605.04207OpenAlexW2963691683MaRDI QIDQ5368767FDOQ5368767

Authors: Mrinal Kumar, Ramprasad Saptharishi, Michael A. Forbes 

Publication date: 10 October 2017

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.

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

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

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)

Cited In (7)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)