文章基本信息

标题：Hitting Sets for Orbits of Circuit Classes and Polynomial Families
本地全文：下载
作者：Chandan Saha ; Bhargav Thankey
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The orbit of an n-variate polynomial f(x) over a field F is the set orb(f):=f(Ax+b):AGL(nF) and bFn . The orbit of a polynomial f is a geometrically interesting subset of the set of affine projections of f. Affine projections of polynomials computable by seemingly weak circuit classes can be quite powerful. For example, the polynomial IMM3d -- the (11) -th entry of a product of d generic 33 matrices -- is computable by a constant-width read-once oblivious algebraic branching program (ROABP), yet every polynomial computable by a size-s general arithmetic formula is an affine projection of IMM3poly(s) [Ben-Or-Cleve, STOC'88]. To our knowledge, no efficient hitting set construction was known for orb(IMM3d) before this work. In this paper, we initiate the study of explicit hitting sets for the orbits of polynomials computable by several natural and well-studied circuit classes and polynomial families. In particular, we give quasi-polynomial time hitting sets for the orbits of: 1. Low-individual-degree polynomials computable by commutative ROABPs. This implies quasi-polynomial time hitting sets for the orbits of the elementary symmetric polynomials and the orbits of multilinear sparse polynomials. 2. Multilinear polynomials computable by constant-width ROABPs. This implies a quasi-polynomial time hitting set for the orbits of the family IMM3d. 3. Polynomials computable by constant-depth, constant-occur formulas. This implies quasi-polynomial time hitting sets for the orbits of multilinear depth-4 circuits with constant top fan-in, and also polynomial-time hitting sets for the orbits of the power symmetric polynomials and the sum-product polynomials. 4. Polynomials computable by occur-once formulas. We say a polynomial has low individual degree if the degree of every variable in the polynomial is at most poly(logn), where n is the number of variables. The first two results are obtained by building upon and strengthening the rank concentration by translation technique of [Agrawal-Saha-Saxena, STOC'13]; the second result additionally uses the merge-and-reduce idea from [Forbes-Shpilka, FOCS'13], [Forbes-Saptharishi-Shpilka, STOC'14]. The proof of the third result applies the algebraic independence based technique of [Agrawal-Saha-Saptharishi-Saxena, STOC'12], [Beecken-Mittmann-Saxena, ICALP'11] to reduce to the case of constructing hitting sets for the orbits of sparse polynomials. A similar reduction using the Shpilka-Volkovich (SV) generator based argument in [Shpilka-Volkovich, STOC'08, APPROX-RANDOM'09] yields the fourth result. The SV generator plays an important role in all the four results.