<p><code>[tl;dr]</code> A lot is known, and it is a very active area! <code>[/tl;dr]</code></p>

<p>It is important to specify the representation of the input polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as <a href="https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Definitions">arithmetic circuits</a> (a.k.a. straight-line programs). And the general case actually boils down to testing whether a given polynomial is the zero polynomial.</p>

<p>There are two main settings that have been studied: the whitebox case in which one has the arithmetic circuit and can inspect it, and the blackbox case in which one knows some things about the circuit (size, formal degree, ...) but cannot inspect it, only evaluate it on some values. </p>

<p>Here are some of the restrictions on the circuits that have been studied:</p>

<ul>
<li>Bounded depth: The depth of a circuit is the longest path from an input to the output gate. Testing circuits of depth $2$ is trivial, depth $3$ is very well understood (completely solved? I do not know...), depth $4$ is also well understood. There are results showing that solving the problem for depth-$3$ and depth-$4$ circuit is almost the same as solving the general case.</li>
<li>Top/bottom fan-in: For bounded-depth circuits, many results have been proved when the fan-in (or arity, that is the number of inputs to a given gate) of either the top gate or the bottom gates is bounded.</li>
<li>Other restrictions such as a bound on the number of times a variable is used have also been studied.</li>
</ul>

<p>This <a href="http://arxiv.org/abs/1401.0976">survey by Nitin Saxena</a> is a good source for these results. Note though that it is already more than one year (!) old, and this is a very active area. So the most recent results are not covered.</p>

<p>Finally, there are links between the derandomization of PIT and the derandomization of other problems:</p>

<ul>
<li><a href="http://arxiv.org/abs/1209.5993">Noether's Normalization Lemma</a>, by Ketan D. Mulmuley;</li>
<li><a href="http://eccc.hpi-web.de/report/2014/001/">Multivariate Polynomial Factorization</a>, by Swastik Kopparty, Shubhangi Saraf and Amir Shpilka.</li>
</ul>

CC BY-SA 3.0
2018-04-16T03:45:29.713Z
how large is the straightline program?
Turbo
CC BY-SA 3.0
2015-04-19T10:45:35.667Z
2015-04-19T10:45:35.667Z
Bruno
<p>In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x_1,\dots,x_n]$. Derandomizing known efficient randomized algorithms and producing an efficient deterministic algorithm is an important open problem. Is there a complete problem for PIT so that derandomizing identity testing for this one class of polynomials solves this open problem? If not, are there classes of polynomials where this problem is solved and classes where they are open?</p>

<derandomization><polynomials>
On derandomizing polynomial identity testing
Turbo
# On derandomizing polynomial identity testing

(Asked by: username_0 on 2015-04-19)

In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x\_1,\dots,x\_n]$. Derandomizing known efficient randomized algorithms and producing an efficient deterministic algorithm is an important open problem. Is there a complete problem for PIT so that derandomizing identity testing for this one class of polynomials solves this open problem? If not, are there classes of polynomials where this problem is solved and classes where they are open?

**Tags:** derandomization, polynomials

---

## 1 answers

### Answer by username_1 on 2015-04-19. Score: 10

`[tl;dr]` A lot is known, and it is a very active area! `[/tl;dr]`

It is important to specify the representation of the input polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as [arithmetic circuits](https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Definitions) (a.k.a. straight-line programs). And the general case actually boils down to testing whether a given polynomial is the zero polynomial.

There are two main settings that have been studied: the whitebox case in which one has the arithmetic circuit and can inspect it, and the blackbox case in which one knows some things about the circuit (size, formal degree, ...) but cannot inspect it, only evaluate it on some values.

Here are some of the restrictions on the circuits that have been studied:

* Bounded depth: The depth of a circuit is the longest path from an input to the output gate. Testing circuits of depth $2$ is trivial, depth $3$ is very well understood (completely solved? I do not know...), depth $4$ is also well understood. There are results showing that solving the problem for depth-$3$ and depth-$4$ circuit is almost the same as solving the general case.
* Top/bottom fan-in: For bounded-depth circuits, many results have been proved when the fan-in (or arity, that is the number of inputs to a given gate) of either the top gate or the bottom gates is bounded.
* Other restrictions such as a bound on the number of times a variable is used have also been studied.

This [survey by Nitin Saxena](http://arxiv.org/abs/1401.0976) is a good source for these results. Note though that it is already more than one year (!) old, and this is a very active area. So the most recent results are not covered.

Finally, there are links between the derandomization of PIT and the derandomization of other problems:

* [Noether's Normalization Lemma](http://arxiv.org/abs/1209.5993), by Ketan D. Mulmuley;
* [Multivariate Polynomial Factorization](http://eccc.hpi-web.de/report/2014/001/), by Swastik Kopparty, Shubhangi Saraf and Amir Shpilka.

> **Comments:**
> **username_0**: how large is the straightline program?  

---

