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ⁿ\). 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 \ (IMM₃, ₃\) —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 \ (IMM₃, ₏₎₋ₘ (s) \) as shown by Ben-or and Cleve 12. To our knowledge, no efficient hitting set construction was known for \ (orb (IMM₃, ₃) \) 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 \ (IMM₃, ₃ ₃ ₍\). 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 (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.