By Julia Schwarz
Pravesh Kothari has joined the Princeton faculty, bringing experience in theoretical computer science and algorithm design.
Kothari’s interest in theoretical computer science started as an undergraduate at the Indian Institute of Technology in Kanpur, India where he took a class on algorithms with Surender Baswana. At the time, Kothari was very involved in programming competitions, and took the class because he thought it would teach him how to program better. Instead, he developed a lasting interest in algorithms.
“I was struck by the beauty of algorithm design,” said Kothari. “I decided I wanted to work on theoretical computer science forever.”
He went on to complete a doctorate at the University of Texas-Austin and spent four years as an assistant professor at Carnegie Mellon University before coming to Princeton in January 2024. His work has been recognized with a Presburger Award from the European Association for Theoretical Computer Science, an Alfred P. Sloan Foundation Fellowship and an NSF CAREER Award.
His research focuses on algorithm design, particularly average-case optimization. In the 1970s, Kothari said, mathematicians realized that many difficult algorithmic problems could not be solved perfectly in every scenario. By the mid-1990s, they began to design algorithms that could solve a problem quickly and efficiently most of the time given an average input. These algorithms, according to Kothari, are designed to be specific enough to solve an average problem and general enough to be broadly useful across applications in computer science.
One recent algorithmic problem Kothari has been working on is finding dense communities in networks — for example, finding a small group of people who are friends with each other on Facebook, which has one billion users. According to Kothari, this is “already known to be a hard problem to solve in the worst-case, even approximately.” In a series of papers published in the last five years, Kothari has finally found near-optimal solutions for the problem using general semirandom input models, some of which were proposed by researchers in the 1990s.
More recently, his work has been motivated by surprising connections between algorithm design and seemingly unrelated problems in other areas of mathematics. While working on new algorithms for semirandom models of the satisfiability problem — a classic hard mathematical problem in theoretical computer science — he discovered that the resulting methods also confirm important conjectures in combinatorics and coding theory.
“This connection came entirely out of left field,” said Kothari. “We were able to prove a bunch of things that people had been working on for more than 20 years.” It turns out that work on algorithms, he said, can solve more than algorithmic problems.
In the spring, Kothari will be teaching a new course, COS598I: Advanced Topics in Computer Science: Matrix Concentration and Applications. The course will cover random matrix theory, an area of mathematics that is typically taught in other disciplines. Kothari’s goal is to teach the subject with a new focus on its applications to computer science.