Subhash Khot named a 2016 MacArthur Fellow

Our former colleague Subhash Khot, now at the Courant Institute of New York University, was named a 2016 MacArthur Fellow. The MacArthur Fellowships are an annual prize awarded by the John D. and Catherine T. MacArthur Foundation to individuals that have shown extraordinary originality and dedication in their creative pursuits. 

From the citation: Subhash Khot is a theoretical computer scientist whose work is providing critical insight into unresolved problems in the field of computational complexity. Since the 1970s, one of the major questions in theory of computing has been whether or not P = NP. That is, can every problem whose solution can be quickly verified by a computer also be quickly solved by a computer? Most computer scientists believe that P does not equal NP—that there are problems, known as NP-hard problems, for which a solution cannot be found efficiently by an algorithm. Thousands of practical problems, from the best way to design a computer chip to optimal airplane schedules, have been shown to be NP-hard.