Current Science

Manindra Agrawal ¹

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

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.

Full Text