Forbes, Michael A. ;
Kumar, Mrinal ;
Saptharishi, Ramprasad
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 in F[x_1, x_2, ..., 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 = P as formal polynomials. In this paper, we study the question of proving lower bounds for homogeneous depth3 and depth4 arithmetic circuits for functional computation. We prove the following results:
1. Exponential lower bounds for homogeneous depth3 arithmetic circuits for a polynomial in VNP.
2. Exponential lower bounds for homogeneous depth4 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 depth4 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 [Kumar/Saptharishi, ECCC 2015] that over constant sized finite fields, strong enough {average case} functional lower bounds for homogeneous depth4 circuits imply superpolynomial lower bounds for homogeneous depth5 circuits.
Our proofs are based on a family of new complexity measures called shifted evaluation dimension, and might be of independent interest.
BibTeX  Entry
@InProceedings{forbes_et_al:LIPIcs:2016:5826,
author = {Michael A. Forbes and Mrinal Kumar and Ramprasad Saptharishi},
title = {{Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {33:133:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5826},
URN = {urn:nbn:de:0030drops58266},
doi = {10.4230/LIPIcs.CCC.2016.33},
annote = {Keywords: boolean circuits, arithmetic circuits, lower bounds, functional computation}
}
19.05.2016
Keywords: 

boolean circuits, arithmetic circuits, lower bounds, functional computation 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

19.05.2016 