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.STACS.2020.47
URN: urn:nbn:de:0030-drops-119084
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11908/
Chillara, Suryajith
On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits
Abstract
In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of r (referred to as multi-r-ic circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better and better bounds as the value of r increases.
Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing a multilinear polynomial on n^O(1) variables and degree d=o(n), must have size at least (n/r^1.1)^Ω(√{d/r}) when r is o(d) and is strictly less than n^1.1. This bound however deteriorates with increasing r. It is a natural question to ask if we can prove a bound that does not deteriorate with increasing r or a bound that holds for a larger regime of r.
We here prove a lower bound which does not deteriorate with r, however for a specific instance of d = d(n) but for a wider range of r. Formally, we show that there exists an explicit polynomial on n^O(1) variables and degree Θ(log² n) such that any depth four circuit of bounded individual degree r<n^0.2 must have size at least exp(Ω(log² n)). This improvement is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).
BibTeX - Entry
@InProceedings{chillara:LIPIcs:2020:11908,
author = {Suryajith Chillara},
title = {{On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {47:1--47:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11908},
URN = {urn:nbn:de:0030-drops-119084},
doi = {10.4230/LIPIcs.STACS.2020.47},
annote = {Keywords: Lower Bounds, Multilinear, Multi-r-ic}
}
|
Keywords: |
|
Lower Bounds, Multilinear, Multi-r-ic |
|
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.03.2020 |
