Manindra Agrawal is an Indian computer scientist known for his significant contributions to the fields of theoretical computer science and algorithms. He is particularly recognized for his work in number theory and computational complexity. Agrawal is one of the co-inventors of the AKS primality test, which is a groundbreaking algorithm that determines whether a number is prime in polynomial time.
Articles by others on the same topic
Manindra Agrawal coauthored Primality and Identity Testing via Chinese Remaindering by Manindra Agrawal and Somenath Biswas with Somenath Biswas in 2003. The paper connects primality testing to polynomial identity testing, using randomized algorithms for circuit-represented polynomials over finite fields, the rationals and, for one procedure, integers modulo an arbitrary candidate.[ref]
The computational problem is not simply evaluating an already expanded polynomial: a compact arithmetic circuit may encode exponentially many polynomial coefficients. A successful test must exploit that representation without materializing the expansion. This distinction connects an algebraic identity to an implementable randomized algorithm.