The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{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 $\mathrm{IMM}_{3,d}$ -- the $(1,1)$-th entry of a product of $d$ generic $3 \times 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 $\mathrm{IMM}_{3,\mathrm{poly}(s)}$ [Ben-Or-Cleve, STOC'88]. To our knowledge, no efficient hitting set construction was known for $\mathrm{orb}(\mathrm{IMM}_{3, d})$ 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 $\mathrm{IMM}_{3,d}$.

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 $\mathrm{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-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.

We have removed the individual degree restriction from our third and fourth results by invoking the hitting set for the orbits of sparse polynomials in the independent and simultaneous work by Medini and Shpilka (2021). In the original version of our work, we had instead applied our first result on commutative ROABPs (specialized to the case of sparse polynomials).

Abstract of the previous revision was not edited properly; it can be ignored.

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{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 $\mathrm{IMM}_{3,d}$ -- the $(1,1)$-th entry of a product of $d$ generic $3 \times 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 $\mathrm{IMM}_{3,\mathrm{poly}(s)}$ [Ben-Or-Cleve, STOC'1988]. To our knowledge, no efficient hitting set construction was known for $\mathrm{orb}(\mathrm{IMM}_{3, d})$ before this work.

In this paper, we initiate the study of explicit hitting sets for the \emph{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 \emph{commutative ROABPs}. This implies quasi-polynomial time hitting sets for the orbits of the \emph{elementary symmetric polynomials} and the orbits of \emph{multilinear sparse polynomials}.

2. Multilinear polynomials computable by \emph{constant-width ROABPs}. This implies a quasi-polynomial time hitting set for the orbits of the family $\mathrm{IMM}_{3,d}$.

3. Polynomials computable by \emph{constant-depth, constant-occur formulas}. This implies quasi-polynomial time hitting sets for the orbits of \emph{multilinear depth-4 circuits with constant top fan-in}, and also poly-time hitting sets for the orbits of the \emph{power symmetric polynomials} and the \emph{sum-product polynomials}.

4. Polynomials computable by \emph{occur-once formulas}.

We say a polynomial has low individual degree if the degree of every variable in the polynomial is at most $\mathrm{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-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.
In this work, we give efficient constructions of hitting sets for the orbits of several interesting 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 ROABP. This implies quasi-polynomial time hitting sets for the orbits of multilinear sparse polynomials and the orbits of the elementary symmetric polynomials.

2. Multilinear polynomials computable by constant-width ROABP. This implies a quasi-polynomial time hitting set for the orbit of $\mathrm{IMM}_{3,d}$.

3. Polynomials computable by constant-depth, constant-occur formulas with low-individual-degree sparse polynomials at the leaves. This implies quasi-polynomial time hitting sets for the orbits of multilinear depth-4 circuits with constant top fan-in, and also poly-time hitting sets for the orbits of the power symmetric polynomials and the sum-product polynomials.

4. Polynomials computable by occur-once formulas with low-individual-degree sparse polynomials at the leaves.

We say a polynomial has low individual degree if the degree of every variable in the polynomial is at most $\mathrm{poly}(\log n)$, where $n$ is the number of variables.

The first two results are obtained by building upon the rank concentration by translation technique of [Agrawal-Saha-Saxena, STOC'13]; the second result also uses the merge-and-reduce idea from [Forbes-Shpilka, APPROX'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 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.

We have removed the individual degree restriction from our third and fourth results by invoking the hitting set for the orbits of sparse polynomial in the independent and simultaneous work by Medini and Shpilka (2021). In the original version of our work, we had instead applied our first result on commutative ROABPs (specialized to the case of sparse polynomials).

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{F}^n\}$. This paper studies explicit hitting sets for the orbits of polynomials computable by certain well-studied circuit classes. This version of the hitting set problem is interesting as $\mathrm{orb}(f)$ is a natural 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 $\mathrm{IMM}_{3,d}$ -- the $(1,1)$-th entry of a product of $d$ generic $3 \times 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 $\mathrm{IMM}_{3,\mathrm{poly}(s)}$. To our knowledge, no efficient hitting set construction was known for even $\mathrm{orb}(\mathrm{IMM}_{3, d})$ before this work.

In this work, we give efficient constructions of hitting sets for the orbits of several interesting 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 ROABP. This implies quasi-polynomial time hitting sets for the orbits of multilinear sparse polynomials and the orbits of the elementary symmetric polynomials.

2. Multilinear polynomials computable by constant-width ROABP. This implies a quasi-polynomial time hitting set for the orbit of $\mathrm{IMM}_{3,d}$.

3. Polynomials computable by constant-depth, constant-occur formulas with low-individual-degree sparse polynomials at the leaves. This implies quasi-polynomial time hitting sets for the orbits of multilinear depth-4 circuits with constant top fan-in, and also poly-time hitting sets for the orbits of the power symmetric polynomials and the sum-product polynomials.

4. Polynomials computable by occur-once formulas with low-individual-degree sparse polynomials at the leaves.

We say a polynomial has low individual degree if the degree of every variable in the polynomial is at most $\mathrm{poly}(\log n)$, where $n$ is the number of variables.

The first two results are obtained by building upon the rank concentration by translation technique of [Agrawal-Saha-Saxena, STOC'13]; the second result also uses the merge-and-reduce idea from [Forbes-Shpilka, APPROX'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 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.