Name
Abstract | ||
|---|---|---|
We show here a 2Ω(√d ⋅ log N) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d3 in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Σi ∏j Qij, where the Qij's are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that ∑i, j (Number of monomials of Qij)) ≥2Ω(√d ⋅log N). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on recent lower bound results [1], [2], [3], [4], [5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound from an earlier work of the same authors and the NΩ(log log N) lower bound in the independent work of [7]. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/FOCS.2014.15 | Foundations of Computer Science |
Keywords | Field | DocType |
circuit complexity,0,1-coefficients,2Ω(√d·log N) size lower bound,Nisan-Wigderson design-based family,complexity class VNP,homogeneous depth arithmetic formulas,homogeneous polynomials,Arithmetic circuits,lower bounds,shifted partial derivatives | Log-log plot,Complexity class,Discrete mathematics,Binary logarithm,Combinatorics,Exponential function,Polynomial,Homogeneous,Upper and lower bounds,Arithmetic,Monomial,Mathematics | Conference |
Volume | Issue | ISSN |
46 | 1 | 0272-5428 |
Citations | PageRank | References |
21 | 0.75 | 27 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Chandan Saha | 3 | 227 | 16.91 |
| Srikanth Srinivasan | 4 | 132 | 21.31 |