Polynomial-size explicit hitting sets for depth-3 (ΣΠΣ) arithmetic circuits over ℚ
Equivalent in strength to proving algebraic circuit lower bounds, but recent constant-depth lower bounds (2021) show real movement, so it is research-grade, below the P vs NP and permanent-vs-determinant problems. Application value is modest because most uses are theoretical derandomisations. Leverage is mid-band: it reshapes derandomisation and algebraic complexity.
The problem
Test whether a formula built from additions and multiplications is secretly zero, with a fixed list of test inputs.
- 1Is this formula secretly zero?
- 2Random test inputs work well
- 3Can a fixed short list do it?
- 4Three layers are the first hard case
- 5Open: efficient fixed list for depth 3
Polynomial identity testing (PIT). Given an arithmetic circuit (a network of additions and multiplications) computing a polynomial, decide whether it computes the zero polynomial. A randomised polynomial-time black-box algorithm follows from the Schwartz–Zippel lemma: a nonzero polynomial of degree is nonzero at a random point from a large enough set with high probability.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Computational complexity theoryTheory · host
- Then
- Polynomial-size explicit hitting sets for depth-3 (ΣΠΣ) arithmetic circuits over ℚThe problem
State of the art
Equivalence with lower bounds. Kabanets and Impagliazzo (STOC 2003; Comput. Complexity 2004) proved that derandomising PIT implies either or that the permanent has no polynomial-size arithmetic circuits; conversely, sufficiently strong explicit lower bounds give hitting sets via algebraic hardness-versus-randomness.
Constant depth. Limaye, Srinivasan and Tavenas (ECCC TR21-081; FOCS 2021) proved the first super-polynomial lower bounds for constant-depth algebraic circuits over fields of characteristic zero and, through the hardness–randomness connection, the first deterministic subexponential-time PIT for constant-depth circuits; together with Andrews and Forbes (STOC 2022) this gives subexponential-size hitting sets for every constant depth. Polynomial-size hitting sets are known only for restricted classes: depth-3 circuits with bounded top fan-in (white-box by Kayal and Saxena, 2007; black-box by Saxena and Seshadhri, 2011–12), sparse polynomials, and quasi-polynomial ones for read-once oblivious algebraic branching programs (Forbes–Shpilka and successors). Guo and Wang (arXiv:2504.15143, 2025, preprint) give deterministic polynomial-time black-box PIT for circuits when one top summand is squarefree. No polynomial-size (or even quasi-polynomial-size) hitting set is known for circuits with unbounded top fan-in.
Realistic applications
Efficient deterministic PIT would derandomise algorithms that reduce to identity testing, such as perfect matching via Tutte or Edmonds matrices, parallel matching algorithms, and some equivalence and interpolation problems, and through Kabanets–Impagliazzo it would come with explicit algebraic lower bounds. Practical impact is small, since randomised PIT is cheap and reliable.
What counts as solved
An explicit, -time constructible hitting set of size for circuits of size over (or over all large fields), with proof accepted by algebraic-complexity experts. A quasi-polynomial-size hitting set for this class is significant partial progress; the same for every constant depth would go beyond the target.
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
The result is a poly(s)-time constructible hitting set of poly(s) size for depth-3 circuits, which is an explicit construction with a correctness proof. Only the proof can establish it, since random testing of small circuits cannot show the hitting-set property, and Mathlib has no arithmetic-circuit formalism. Algebraic-complexity experts review it, and a quasi-polynomial-size set is recorded as partial progress.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Algebraic proof technique; computation helps find small hitting sets but not asymptotics.
Bottlenecks
ranked by votes- #1TheoryLower bounds needed for the hardness–randomness trade-off
Black-box PIT in P implies lower bounds, so hitting sets need new super-polynomial algebraic lower bounds with strong parameters, not just the weak ones currently proved.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Jul 6, 2021Super-polynomial lower bounds for constant-depth algebraic circuitssource
Limaye, Srinivasan and Tavenas proved the first such lower bounds (ECCC TR21-081, July 2021; FOCS 2021).
- Jun 9, 2003PIT derandomisation equals lower boundssource
Kabanets and Impagliazzo proved derandomising PIT implies circuit lower bounds (STOC 2003).