Abstract | ||
---|---|---|
We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition X1⊔⋅⋅⋅⊔ Xd of the variable indices [n] that the top product layer respects, i.e. C(term{x})=∑i=1k ∏j=1d fi,j(term{x}Xj), where fi,j is a sparse polynomial in F[term{x}Xj]. Extending this definition to any depth - we call a depth-D formula C (consisting of alternating layers of Σ and Π gates, with a Σ-gate on top) a set-depth-D formula if every Π-layer in C respects a (unknown) partition on the variables; if D is even then the product gates of the bottom-most Π-layer are allowed to compute arbitrary monomials. In this work, we give a hitting-set generator for set-depth-D formulas (over any field) with running time polynomial in exp((D2log s) Δ - 1), where s is the size bound on the input set-depth-D formula. In other words, we give a quasi-polynomial time blackbox polynomial identity test for such constant-depth formulas. Previously, the very special case of D=3 (also known as set-multilinear depth-3 circuits) had no known sub-exponential time hitting-set generator. This was declared as an open problem by Shpilka & Yehudayoff (FnT-TCS 2010); the model being first studied by Nisan & Wigderson (FOCS 1995) and recently by Forbes & Shpilka (STOC 2012 & ECCC TR12-115). Our work settles this question, not only for depth-3 but, up to depth εlog s / log log s, for a fixed constant ε Hadamard algebra, after applying a 'shift' on the variables. We propose a new algebraic conjecture about the low-support rank-concentration in the latter formulas, and manage to prove it in the case of set-depth-D formulas. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1145/2488608.2488649 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
quasi-polynomial hitting-set,depth-d formula,set-depth-d formula,depth-4 formula,sub-exponential time hitting-set generator,log log,constant-depth formula,input set-depth-d formula,sparse polynomial,quasi-polynomial time blackbox polynomial,latter formula | Log-log plot,Discrete mathematics,Polynomial identity testing,Combinatorics,Open problem,Polynomial,Quasi-polynomial,e,Monomial,Partition (number theory),Mathematics | Conference |
Volume | Citations | PageRank |
abs/1209.2333 | 22 | 0.67 |
References | Authors | |
27 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manindra Agrawal | 1 | 581 | 45.56 |
Chandan Saha | 2 | 227 | 16.91 |
Nitin Saxena | 3 | 280 | 26.72 |