IN August, Manindra Agrawal, a theoretical computer scientist at the Indian Institute of Technology-Kanpur (IIT-K), created sensation in theoretical computer science (TCS) and mathematics circles by solving a problem that goes back to ancient Greek mathematics and which, in recent times, has eluded the best of mathematical minds. In association with his two students, Neeraj Kayal and Nitin Saxena, Agrawal discovered an algorithm that can test for the primality of a given number (whether the number is a prime or not) deterministically and unconditionally in polynomial time (Frontline, August 30). That is, the number of computational steps needed, however large the number may be, grows at best as a power of the problem input size. Input size in this case is measured in terms of the number of bits required to represent the given number, which is roughly the number of digits in the number.
While it was generally believed that a polynomial time algorithm existed, all efforts until now had failed. Existing algorithms either grew exponentially or, if they were polynomial-type, required conditions to be imposed or had finite probability for returning wrong answers. The Agrawal-Kayal-Saxena (AKS) algorithm has none of these shortcomings. It also provides proof of correctness of the answer it yields. The remarkable feature of the AKS algorithm is that it is barely 12 steps long and uses simple undergraduate algebra. In this breakthrough, the two students were responsible for coming up with an ingenious trick to handle the problem. It has been widely hailed as "elegant", "beautiful" and so on. While from the perspective of mathematics the AKS algoritm constitutes a major breakthrough, its practical applicability in areas such as cryptography is still far away as its efficiency is not as good as other algorithms in use. On October 30, Manindra Agrawal was presented the prestigious Clay Research Award of the Clay Mathematical Institute (CMI) for 2002 for this outstanding mathematical achievement. A private foundation incorporated and endowed by London T. Clay and his family in 1998-end in Cambridge, Massachusetts, United States, CMI has as its stated objective "to increase and disseminate mathematical knowledge, to educate mathematicians and other scientists about new discoveries in the field of mathematics, to encourage gifted students to pursue mathematical careers, and to recognise extraordinary achievements and advances in mathematical research."
The CMI presents the award annually as its highest recognition of general achievement in mathematical research to one or more mathematicians. The award takes the form of an elegant bronze replica of a granite sculpture `Figure Eight Knot Complement'. The sculpture represents an object embodying certain complex mathematical ideas. It was commissioned by CMI in 1999 and sculpted by the mathematician-sculptor Helaman Ferguson. Agrawal was one of the two awardees for 2002, the other being the mathematician Oded Schramm, working with Microsoft Inc. Awardees in the past include Andrew Wiles in 1999 (for his proof of the famous Fermat's Theorem), Laurent Lafforgue and Alain Connes in 2000, Stanislav Smirnov and the physicist Edward Witten in 2001.
In his remarks at the presentation ceremony, CMI President Arthur Jaffe (the well-known mathematician and physicist) said: "I invited his students (now in the first few months of their graduate study, but already world-famous) to accompany Agrawal to this meeting. Unfortunately, about three weeks ago, the U.S. State Department denied their visa application, stating that "they gave insufficient proof that after their one-week visit to the United States, they would return to India!"
R. RamachandranCOMMents
COMMents
SHARE