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 depth-3 and depth-4 arithmetic circuits for functional computation. We prove the following results:
1. Exponential lower bounds for 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 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 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.
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:1--33:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-008-8},
ISSN = {1868-8969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5826},
URN = {urn:nbn:de:0030-drops-58266},
doi = {10.4230/LIPIcs.CCC.2016.33},
annote = {Keywords: boolean circuits, arithmetic circuits, lower bounds, functional computation}
}
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 |
19.05.2016