October 6, 2016
Subhash Khot GS ’03, an alumnus of the University’s graduate computer science program, has received the MacArthur Fellowship for his pioneering work in computational complexity.
Khot is currently a professor at New York University’s Courant Institute of Mathematical Sciences. In 2010, he won the Waterman Award, which is awarded for “exceptional individual achievement in scientific or engineering research” of “significant impact on the field so as to situate him or her as a leader among peers.” In 2014, he was awarded the Rolf Nevanlinna Prize by the International Congress of Mathematicians “for outstanding contributions in Mathematical Aspects of Information Sciences.”
Khot’s dissertation, as well as much of his subsequent research, expands greatly on the discussion of P versus NP problem, an open question in computer science regarding the existence of efficient algorithms for general problems.
Khot’s work builds upon that of his doctoral advisor, University professor Sanjeev Arora, and that of Johan Håstad, professor of theoretical computer science at the KTH Royal Institute of Technology in Sweden, with whom Khot worked very closely as a graduate student.
“The next question was whether you can compute approximation solutions, and there’s also been a body of work, and Khot’s work fits in that body [...] whether or not many of these problems have good algorithms for computing approximations of solutions,” Arora noted, given the difficulty of approaching the P vs NP problem and doubt in the field that a positive resolution exists.
When it comes to researching bounds on computational complexity, algorithms have two bounds, an upper and a lower. With the upper bound one can try to design more efficient algorithms than those currently existing. With the lower bounds, one can try to prove that any algorithm which satisfies given constraints must take a given time to run properly. Much of Khot’s work fits into the latter field of research.
Khot formulated what is now known as the Unique Games Conjecture in his dissertation. The Conjecture states that a particular computational problem is “difficult” in the sense that it cannot be efficiently computed. Using this, Khot provided hard lower bounds for the computational complexity of various problems.
“The funny thing about this conjecture is that at first everyone thinks for it to be true, and then it turned out that it had lots and lots of implications, and there were these things you could prove based on it. It took a couple of years before people realized just how powerful this conjecture was,” Håstad said.
The power in the conjecture, Arora explained, comes from the “nice classification of the difficulty of computing approximate solutions to many problems,” which one can derive from it.
When he first came to the University from India, Khot said the campus felt “almost magical.” Looking back upon his time as a graduate student, he described it as “some of the best five years I’ve had.”
He added that he enjoyed the academic environment and the small size of the computer science department.
“[Khot] was one of our best grads ever, and he was very independent from the first year,” Arora noted. “He quickly took on some of the hardest problems in the field and started working on them by the end of his first year.”
Håstad also added that Khot was very independent.
“He was thinking about his own things that he wanted to think about,” Håstad explained.
Khot said that current and future Ph.D. students choosing their thesis topics should make their choices wisely.
“It’s possible that your Ph.D. work will turn out to define a large part of your career… Choose the ones which may sound kind of ambitious at that point, but something that provides a long enough horizon, not just the limited focus of writing the thesis,” he added.
Despite his work in the field of computational complexity, Khot said that his true passion is for mathematics and its applications in other fields, which he focuses on currently as a professor at NYU.
“Both in terms of research and teaching, the institute… gives a very broad view of all of the mathematical sciences together, as opposed to… thinking of different mathematical sciences in isolation,” he added.