<p>If you can solve PIT for a circuit class <span class="math-container">$\mathscr{C}$</span>, this generally lifts to a solution of PIT for <span class="math-container">$\Pi \mathscr{C}$</span>, where <span class="math-container">$\Pi \mathscr{C}$</span> is the set of polynomials <span class="math-container">$f$</span> that can be expressed as <span class="math-container">$f = \prod_i f_i$</span> with <span class="math-container">$f_i \in \mathscr{C}$</span>.</p>
<p>In the white-box case, the PIT algorithm for <span class="math-container">$\Pi \mathscr{C}$</span> is exactly what Josh pointed out in the comments. The product <span class="math-container">$f$</span> is nonzero iff all the factors <span class="math-container">$f_i$</span> are nonzero, and you can see the individual factors <span class="math-container">$f_i$</span>, so you simply run your <span class="math-container">$\mathscr{C}$</span>-PIT algorithm on each factor.</p>
<p>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 <em>hitting set generator</em>. This is a polynomial map <span class="math-container">$\mathcal{G} : \mathbb{F}^\ell \to \mathbb{F}^n$</span> with the property that for every polynomial <span class="math-container">$h \in \mathscr{C}$</span>, the composition <span class="math-container">$h\circ \mathcal{G}$</span> is zero iff <span class="math-container">$h$</span> itself is zero. If a generator <span class="math-container">$\mathcal{G}$</span> hits <span class="math-container">$\mathscr{C}$</span>, then <span class="math-container">$\mathcal{G}$</span> also hits <span class="math-container">$\Pi \mathscr{C}$</span>, as a product of nonzero polynomials remains nonzero. (To obtain a PIT algorithm from a generator, test the composed polynomial <span class="math-container">$f \circ \mathcal{G}$</span> by brute force.)</p>
<p>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 <span class="math-container">$\Pi \Sigma \Pi$</span> circuits.</p>

CC BY-SA 4.0
2024-04-17T20:53:47.483Z
2024-04-17T20:53:47.483Z
Robert Andrews
<p>I am reading a <a href="https://www.cse.iitk.ac.in/users/nitin/papers/pit-survey09.pdf" rel="nofollow noreferrer">survey on polynomial identity testing</a> by Saxena. On page 6 he writes that PIT for depth-3 circuits of the form <span class="math-container">$\prod \sum \prod$</span> 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 &quot;trivial&quot; randomized algorithm via Schwartz-Zippel.</p>

CC BY-SA 4.0
2024-04-13T21:26:09.650Z
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.
Joshua Grochow
CC BY-SA 4.0
2024-04-14T00:03:09.083Z
Wait what I said about blackbox factorization isn't known. Multivariable factorization is equivalent to PIT (Kopparty-Saraf-Shpilka).
Joshua Grochow
CC BY-SA 4.0
2024-04-17T04:31:29.317Z
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!
Anakin Dey
<polynomials><algebraic-complexity>
Polynomial Identity Testing for $\prod \sum \prod$
Anakin Dey
# Polynomial Identity Testing for $\prod \sum \prod$

(Asked by: username_0 on 2024-04-13)

I am reading a [survey on polynomial identity testing](https://www.cse.iitk.ac.in/users/nitin/papers/pit-survey09.pdf) 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.

**Tags:** polynomials, algebraic-complexity
> **Comments:**
> **username_1**: 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.  
> **username_1**: Wait what I said about blackbox factorization isn't known. Multivariable factorization is equivalent to PIT (Kopparty-Saraf-Shpilka).  
> **username_0**: 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!  

---

## 1 answers

### Answer by username_2 on 2024-04-17. Score: 6 | Accepted answer

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.


---

