Events
Colloquium
"The surprising reach of spectral algorithms for smoothed k-SAT"
 |
Speaker: Pravesh Kothari (Princeton) Assistant Professor of Computer Science Princeton University Wednesday, October 1, 2025 11:30AM - 1:00PM Lunch will be served in 1307 at 11:30am
Talk will be in 1327 from 12:00-1:00pm Location: Yale Institute for Foundations of Data Science, Kline Tower 13th Floor, Room 1327, New Haven, CT 06511 and via Webcast: https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=8f04335e-5091-4d34-8c43-b34f013a099a |
Abstract: Semirandom input models are hybrids of the classical worst-case and average-case models in algorithm design. They were introduced in the 1990s to inspire “robust heuristics” that, on the one hand, escape worst-case hardness results, while, on the other, avoid “overfitting” to a specific distribution of input instances. Over the past five years, rapid progress has been made in finding near-optimal algorithms in the harshest known semirandom models for basic problems such as k-SAT and clique. This progress has come about by somewhat surprising, two-way connections to extremal combinatorics.
In this talk, I will primarily focus on smoothed k-SAT, the harshest known semirandom model for the problem introduced by Feige in the early 2000s. I will talk about a new class of spectral methods based on “Kikuchi” matrices that give optimal guarantees for the problem. More excitingly, the new techniques have led to major progress on a growing list of purely combinatorial/coding theoretic problems including Feige’s 2008 conjecture on hypergraph girth vs density tradeoffs, lower bounds on locally decodable and locally correctable codes, sharpest known bounds on the Frantzikinakis-Lesigne-Weirdl conjecture on Szemeredi’s theorem with random common differences, and very recently, the strongest known static data structure lower bounds.
Speaker bio: Pravesh K Kothari received his Ph. D. from the University of Texas at Austin in 2016 after a Bachelor’s degree from Indian Institute of Technology, Kanpur. He is currently an Assistant Professor in the Computer Science Department at Princeton University. Earlier, from 2019-2023, he was an Assistant Professor in the Computer Science Department at Carnegie Mellon University. Dr. Kothari was a Research Instructor of Computer Science jointly hosted by the Institute for Advanced Study, Princeton and the Department of Computer Science at Princeton University from 2016-19.
Dr. Kothari’s research interests span several topics in theoretical computer science such as convex optimization and applications to algorithm design, algorithms and lower bounds for statistical estimation and average-case combinatorial optimization, and spectral methods and connections to random matrix theory, coding theory and extremal combinatorics.
Dr Kothari is a recipient of the Presburger Award (2024), IIT Kanpur Young Alumnus Award (2023), Sloan Fellowship (2022), NSF Career Award (2021), and Simons Award for Graduate students in Theoretical Computer Science (2014).
Add To: Google Calendar | Outlook | iCal File
- Colloquium
Submit an Event
Interested in creating your own event, or have an event to share? Please fill the form if you’d like to send us an event you’d like to have added to the calendar.