TR21-015 Authors: Chandan Saha, Bhargav Thankey

Publication: 16th February 2021 10:54

Downloads: 115

Keywords:

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.