3
$\begingroup$

I am reading a survey on polynomial identity testing by Saxena. On page 6 he writes that PIT for depth-3 circuits of the form $\prod \sum \prod$ is trivial. He gives no citation and as such I believe this should be folklore. However, I am unfamiliar with the lore and haven't come up with a "trivial" randomized algorithm via Schwartz-Zippel.

$\endgroup$
3
  • 1
    $\begingroup$ Given a circuit C of that form, it is identically zero iff one of its factors is zero. If given as a whitebox, you can read the factors off of the circuit description, and then it is reduced to the problem of PIT for sparse polynomials (i.e. $\Sigma \Pi$). As a black box, you can first use polynomial factorization to get the factors. I'm not sure I'd call this trivial, but it reduces - trivially in the whitebox case, nontrivally but by a well-known result in the blackbox case - to a previously solved problem. $\endgroup$ Commented Apr 13 at 21:26
  • $\begingroup$ Wait what I said about blackbox factorization isn't known. Multivariable factorization is equivalent to PIT (Kopparty-Saraf-Shpilka). $\endgroup$ Commented Apr 14 at 0:03
  • $\begingroup$ I missed the part where this was talking about the whitebox case. I've never heard of that equivalence between blackbox multivariable factorization and PIT, I'll have to look into that. Thanks! $\endgroup$
    – Anakin Dey
    Commented Apr 17 at 4:31

1 Answer 1

6
$\begingroup$

If you can solve PIT for a circuit class $\mathscr{C}$, this generally lifts to a solution of PIT for $\Pi \mathscr{C}$, where $\Pi \mathscr{C}$ is the set of polynomials $f$ that can be expressed as $f = \prod_i f_i$ with $f_i \in \mathscr{C}$.

In the white-box case, the PIT algorithm for $\Pi \mathscr{C}$ is exactly what Josh pointed out in the comments. The product $f$ is nonzero iff all the factors $f_i$ are nonzero, and you can see the individual factors $f_i$, so you simply run your $\mathscr{C}$-PIT algorithm on each factor.

The black-box case is easy, once the right definitions are in place. Up to some mild loss in parameters, you can assume that your black-box PIT algorithm is given by a hitting set generator. This is a polynomial map $\mathcal{G} : \mathbb{F}^\ell \to \mathbb{F}^n$ with the property that for every polynomial $h \in \mathscr{C}$, the composition $h\circ \mathcal{G}$ is zero iff $h$ itself is zero. If a generator $\mathcal{G}$ hits $\mathscr{C}$, then $\mathcal{G}$ also hits $\Pi \mathscr{C}$, as a product of nonzero polynomials remains nonzero. (To obtain a PIT algorithm from a generator, test the composed polynomial $f \circ \mathcal{G}$ by brute force.)

For the specific case in the original question, Klivans and Spielman (STOC 2001) constructed a hitting set generator for sparse polynomials. The same generator hits $\Pi \Sigma \Pi$ circuits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.