Paper Info
Title
Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree.
Abstract
•A finer product decomposition for Homogeneous Formulas of small depth.•A finer product decomposition for small-depth homogeneous multi-r-ic formulas.•We give superpolynomial lower bounds for homogeneous multi-r-ic formulas of small-depth.•For all Δ∈[ω(1),o(log⁡nlog⁡r)] our lower bound is asymptotically better than Kayal et al. [STOC 2014].
Year
DOI
Venue
2020
10.1016/j.ipl.2019.105900
Information Processing Letters
Keywords
Field
DocType
Algebraic complexity theory,Lower bounds,Theory of computation,Computational complexity
Discrete mathematics,Combinatorics,Theory of computing,Polynomial,Homogeneous,Upper and lower bounds,Multilinear map,Mathematics,Bounded function
Journal
Volume
ISSN
Citations 
156
0020-0190
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Suryajith Chillara1143.68