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 multiric 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 Multiric Depth Four Circuits}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {47:147:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11908},
URN = {urn:nbn:de:0030drops119084},
doi = {10.4230/LIPIcs.STACS.2020.47},
annote = {Keywords: Lower Bounds, Multilinear, Multiric}
}
Keywords: 

Lower Bounds, Multilinear, Multiric 
Collection: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 
Issue Date: 

2020 
Date of publication: 

04.03.2020 