Current Science

Open Access Open Access  Restricted Access Subscription Access

A brief history of polynomial identity testing


Affiliations
1 Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur 208 016, India
 

Polynomial identity testing is the problem of deciding if a given (multivariate) polynomial is identically zero. Over the past decade, connections of this problem with a fundamental issue of complexity theory have been discovered and so the problem has attracted a lot of attention. In this article, we provide a brief history of the problem and its current status.

Keywords

Arithmetic Circuits, Black-Box Algorithm, Complexity Theory, Polynomial Identity Testing.
User
Notifications
Font Size

Abstract Views: 303

PDF Views: 79




  • A brief history of polynomial identity testing

Abstract Views: 303  |  PDF Views: 79

Authors

Manindra Agrawal
Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur 208 016, India

Abstract


Polynomial identity testing is the problem of deciding if a given (multivariate) polynomial is identically zero. Over the past decade, connections of this problem with a fundamental issue of complexity theory have been discovered and so the problem has attracted a lot of attention. In this article, we provide a brief history of the problem and its current status.

Keywords


Arithmetic Circuits, Black-Box Algorithm, Complexity Theory, Polynomial Identity Testing.



DOI: https://doi.org/10.18520/cs%2Fv106%2Fi12%2F1693-1695