ECCC-Report TR09-101https://eccc.weizmann.ac.il/report/2009/101Comments and Revisions published for TR09-101en-usThu, 22 Oct 2009 05:53:11 +0200
Paper TR09-101
| Progress on Polynomial Identity Testing |
Nitin Saxena
https://eccc.weizmann.ac.il/report/2009/101Polynomial identity testing (PIT) is the problem of checking whether a given
arithmetic circuit is the zero circuit. PIT ranks as one of the most important
open problems in the intersection of algebra and computational complexity. In the last
few years, there has been an impressive progress on this problem but a complete
solution might take a while. In this article we give a soft survey exhibiting the ideas
that have been useful.Thu, 22 Oct 2009 05:53:11 +0200https://eccc.weizmann.ac.il/report/2009/101