License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.33
URN: urn:nbn:de:0030-drops-58266
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5826/
Go to the corresponding LIPIcs Volume Portal

Forbes, Michael A. ; Kumar, Mrinal ; Saptharishi, Ramprasad

Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity

pdf-format:
5.pdf (0.6 MB)

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
Collection: 31st Conference on Computational Complexity (CCC 2016)
Issue Date: 2016
Date of publication: 19.05.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI