MPS Awardee Spotlight: Subhash Khot

Subhash Khot, a professor of computer science at New York University’s Courant Institute of Mathematical Sciences, conducts research on hardness of approximation and probabilistically checkable proofs. He is a 2015 Simons Investigator in Theoretical Computer Science and one of 13 principal investigators in the Simons Collaboration on Algorithms and Geometry (A&G), which brings together experts in mathematics and theoretical computer science.

According to Khot, the A&G collaboration has prompted some ambitious long-term projects. By investing energy in understanding each other’s areas and ideas, investigators gain a new perspective for their own work. “Usually people are expert in a specific area and are well aware of the most challenging questions as well as the limitations of current techniques in that area,” he says. “They are often thinking about these problems for years, perhaps decades, and unable to make further progress. By interacting with people with different backgrounds and research interests, they can discover connections that might exist. Once in a while, one stumbles upon unexpected connections between two areas that greatly benefit both.”

Much of Khot’s own work lies at the interface of mathematics and computer science. Recently, in collaboration with Muli Safra, a professor of computer science and Dor Minzer, a graduate student, both at Tel Aviv University, Khot studied a computer science problem called monotonicity testing that might be stated as follows: Given a function on the Boolean hypercube, you want to test whether this function is monotone, that is, entirely increasing or entirely decreasing, by looking at as few values of the function as possible. It turns out that this problem, quite unexpectedly, is closely connected to isoperimetric problems that are central to geometry. In Euclidean space — the space we live in — we know that if we have an object with a fixed volume, its surface area is at least equal to the surface area of a sphere with this volume. But in other spaces, where we have a notion of volume and of surface area, what object of fixed volume has the smallest surface area? The question can be asked in many different geometric spaces, including the Boolean hypercube, which is of particular importance in theoretical computer science. By proving new variants of known isoperimetric results on the hypercube, Khot and his collaborators were able to design the best possible algorithm for the monotonicity testing problem.

“This is one question that I recently worked on, and we solved the problem,” Khot says. “We were very happy with it, and it shows the connections between computer science and mathematics really, really closely. In the context of this problem, and there are more examples, computer science and mathematics go hand in hand — it’s difficult to say which inspired which.”