Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits


Prateek Dwivedi October 29, 2021.


Deterministically solving the Polynomial Identity Testing (PIT) problem is a fundamental computational problem, and it is of pivotal importance in Algebraic Complexity Theory. This intrinsically difficult problem has found its way into many areas of Computer Science. In this talk, we will introduce the problem from the perspective of Algebraic Complexity Theory, discuss its motivations and connections.

Despite decades of effort, there has been little progress on the problem in general. Moreover, under strong restrictions on the circuits, we already have very efficient algorithms. One such well-motivated restriction we consider is depth-4 circuits. Special cases of these circuits are a great source of inspiration for ideas of designing PIT algorithms. However, their inapplicability led us to examine from a different viewpoint. In the talk, we will share these ideas, which helped us in designing efficient algorithms. Further, we will exhibit our newly developed paradigm for designing PIT algorithms.

The results in this talk are a joint work with Pranjal Dutta (CMI & IIT Kanpur) and Nitin Saxena (IIT Kanpur). They appeared in CCC 2021 earlier this year.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Are quantum speedups for learning expressive classes possible?
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • On Probabilistic Approximations of Boolean Functions via Polynomials, and Polynomial Closure Statements over the Boolean Cube
  • Demystifying the border of depth-3 algebraic circuits
  • Derandomization from Time-Space Tradeoffs