Paper Info
Title
On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits
Abstract
AbstractIn this article, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which the polynomial computed at every node has a bound on the individual degree of r≥ 1 with respect to all its variables (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 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 an explicit multilinear polynomial on nO(1) variables and degree d must have size at least (n/r1.1)Ω(√d/r). This bound, however, deteriorates as the value of r increases. It is a natural question to ask if we can prove a bound that does not deteriorate as the value of r increases, or a bound that holds for a larger regime of r.In this article, we prove a lower bound that does not deteriorate with increasing values of r, albeit for a specific instance of d = d(n) but for a wider range of r. Formally, for all large enough integers n and a small constant η, we show that there exists an explicit polynomial on nO(1) variables and degree Θ (log2 n) such that any depth four circuit of bounded individual degree r ≤ nη must have size at least exp(Ω(log2 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).
Year
DOI
Venue
2020
10.1145/3460952
ACM Transactions on Computation Theory
Keywords
DocType
Volume
Lower Bounds,Multilinear,Multi-r-ic
Journal
13
Issue
ISSN
Citations 
3
1942-3454
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Suryajith Chillara1143.68