Hitting Sets for Orbits of Circuit Classes and Polynomial Families

The orbit of an n -variate polynomial \(f({x})\) over a field \(F\) is the set \(orb(f) := f(A{x}+{b}) : A ∈ GL(n,F) and {b}∈ F^n\) . 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 \(IMM3,d\) —the \((1,1)\) th entry of a product of d generic \(3 × 3\) 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 \(IMM3,poly(s)\) as shown by Ben-or and Cleve [ 12 ]. To our knowledge, no efficient hitting set construction was known for \(orb(IMM3, d)\) before this work. In this article, 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: 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 . Multilinear polynomials computable by constant-width ROABPs . This implies a quasi-polynomial time hitting set for the orbits of the family \( IMM3,d d ∈ N\) . 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 . 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(log n)\) , 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, and Saxena [ 6 ]; the second result additionally uses the merge-and-reduce idea from Forbes and Shpilka [ 30 ] and Forbes, Shpilka, and Saptharishi [ 27 ]. The proof of the third result adapts the algebraic independence-based technique of Agrawal, Saha, Saptharishi, and Saxena [ 5 ] and Beecken, Mittmann, and Saxena [ 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 and Volkovich [ 90 ] yields the fourth result. The SV generator plays an important role in all four results.