Quasi-polynomial hitting-set for set-depth- formulas
From MaRDI portal
Publication:5495802
DOI10.1145/2488608.2488649zbMATH Open1293.94140arXiv1209.2333OpenAlexW1984806876MaRDI QIDQ5495802FDOQ5495802
Authors: Chandan Saha, Nitin Saxena, Manindra Agrawal 
Publication date: 7 August 2014
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Abstract: We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition (X_1,...,X_d) of the variable indices [n] that the top product layer respects, i.e. C(x) = sum_{i=1}^k prod_{j=1}^{d} f_{i,j}(x_{X_j}), where f_{i,j} is a sparse polynomial in F[x_{X_j}]. Extending this definition to any depth - we call a depth-Delta formula C (consisting of alternating layers of Sigma and Pi gates, with a Sigma-gate on top) a set-depth-Delta formula if every Pi-layer in C respects a (unknown) partition on the variables; if Delta is even then the product gates of the bottom-most Pi-layer are allowed to compute arbitrary monomials. In this work, we give a hitting-set generator for set-depth-Delta formulas (over any field) with running time polynomial in exp(({Delta}^2 log s)^{Delta - 1}), where s is the size bound on the input set-depth-Delta 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 Delta=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). Our work settles this question, not only for depth-3 but, up to depth epsilon.log s / loglog s, for a fixed constant epsilon < 1. The technique is to investigate depth-Delta formulas via depth-(Delta-1) formulas over a 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-Delta formulas.
Full work available at URL: https://arxiv.org/abs/1209.2333
Recommendations
- Subexponential size hitting sets for bounded depth multilinear formulas
- scientific article; zbMATH DE number 6829282
- Arithmetic circuits with locally low algebraic rank
- Arithmetic circuits with locally low algebraic rank
- A note on parameterized polynomial identity testing using hitting set generators
Cited In (15)
- Derandomization and absolute reconstruction for sums of powers of linear forms
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Title not available (Why is that?)
- Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
- Improved Explicit Hitting-Sets for ROABPs
- Title not available (Why is that?)
- Subexponential size hitting sets for bounded depth multilinear formulas
- Exact learning from an honest teacher that answers membership queries
- Blackbox identity testing for sum of special ROABPs and its border class
- Title not available (Why is that?)
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- Read-once polynomial identity testing
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- Improved hitting set for orbit of ROABPs
This page was built for publication: Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495802)
