Posted by Rob Knies

Neeraj Kayal 

Life consists, in large part, of seeking answers to the questions that perplex us, and Neeraj Kayal is no exception. But for Kayal, a researcher at Microsoft Research India, those questions can take a distinctly singular direction.

Such as: What is the fastest way to solve a system of linear equations? A system of polynomial equations?

Or: Can we factor integers efficiently?

Or: How can we tackle rounding errors in numerical computation? For an algorithm whose final answer is either yes or no, can we rewrite it in such a way that rounding the results of intermediate computations to a reasonable amount of precision does not affect the final answer?

Kayal’s research is in theoretical computer science with a focus on arithmetic complexity, and his pursuit of answers to such questions has led the Indian National Science Academy (INSA) to include him in its list of recipients of the 2012 INSA Medal for Young Scientists, presented to young scientists of extraordinary promise and creativity who have made notable research contributions in science and technology.

The citation for Kayal’s honor mentions his work in the development of arithmetic-complexity theory and its connection with arithmetic lower bounds. “He has developed,” the citation states, “a deterministic algorithm for prime numbers, the resolution of the constant fanin conjecture for depth-three circuits, and a reconstruction of arithmetic formulas.”

Yet for all those accomplishments, Kayal did not have a handy algorithm at hand to help him gauge the torrent of well wishes he would experience once the news was out.

“When I mentioned it in passing to my manager, Satya Lokam, a few days after learning about it,” Kayal recalls, “I was quite surprised by all the congratulatory messages that poured in.”

For Microsoft Research India, the award was the second in two years. In 2011, fellow researcher Nisheeth Vishnoi was similarly honored.

“It is great to see young scientists like Neeraj Kayal and Nisheeth Vishnoi get this type of recognition,” says P. Anandan, Microsoft distinguished scientist and managing director of Microsoft Research India. “It reinforces our faith in the Microsoft Research model for a research lab: Hire the best people, and give them an intellectually free and vibrant environment in which they can do their work.

“Congratulations, Neeraj!”

For Kayal, though, the recognition is merely a pleasant diversion along his career path of untangling the complexity of arithmetic functions.

“One of the goals in arithmetic complexity,” he explains, “has been to prove impossibility conjectures such as ‘The permanent polynomial cannot be efficiently computed using a small number of additions, subtractions, and multiplications.'

“While this is a natural scientific and mathematical challenge, on the face of it, this pursuit seems to be practically useless. If I am interested in efficiently computing some other function g(x), resolving the above conjecture seems to be of no help in finding an (approximately) optimal way to compute g(x).”

Nevertheless, such inquiries can prove valuable.

“My recent work has shown that impossibility results of the kind we seek can often be used to devise efficient algorithms for the latter problem,” Kayal says. “There are some restricted models of computation where we can, indeed, prove ‘good’ lower bounds for the permanent polynomial, and my work has shown how the mathematical insights from these lower-bound proofs can help find the optimal way to compute a given function g(x) in that model of computation.”

The medal is accompanied by a small research grant from INSA, and Kayal is calculating how to use it most efficiently.

“I am trying to see,” he concludes, “if this can be redirected to support a Ph.D. student in a nearby academic institute.”