Email: mitalib at cs dot washington dot edu
Office: Gates Center 211
About
I am a theoretical computer scientist and an Assistant Professor in the Allen School of Computer Science & Engineering at the University of Washington. My research explores complexity theory and algorithms and I am particularly interested in approximation algorithms, probabilistically checkable proofs, and high-dimensional expanders.
I received my undergrad degree from IIT Madras and my Ph.D. in Computer Science from Harvard University in 2022, advised by Prof. Madhu Sudan. After that, I was a postdoc at CMU, hosted by Professors Aayush Jain and Pravesh Kothari, followed by a postdoc in the MIT Department of Mathematics.
Publications
-
Quasi-Linear Size PCPs with Small Soundness from HDX.
with Dor Minzer and Nikhil Vyas (Appendix D by Zhiwei Yun)
STOC 2025 (Best Paper Award) -
Rounding Large Independent Sets on Expanders.
with Tim Hsieh and Pravesh Kothari
STOC 2025 -
Constant Degree Networks for Almost-Everywhere Reliable Transmission.
with Dor Minzer
STOC 2025 -
Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity.
with Karthik C. S. and Dor Minzer
STOC 2025 -
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures.
with Prashanti Anderson, Rares-Darius Buhai, Pravesh Kothari and David Steurer -
Constant Degree Direct Product Testers with Small Soundness.
with Noam Lifshitz and Dor Minzer
FOCS 2024 -
Characterizing Direct Product Testing via Coboundary Expansion.
with Dor Minzer
STOC 2024 -
Solving Unique Games over Globally Hypercontractive Graphs.
with Dor Minzer
CCC 2024 -
Polynomial-Time Power-Sum Decomposition of Polynomials.
with Tim Hsieh, Pravesh Kothari and Jeff Xu
FOCS 2022 -
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments.
with Max Hopkins, Tali Kaufman and Shachar Lovett
STOC 2022 -
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games.
with Max Hopkins, Tali Kaufman and Shachar Lovett
SODA 2022 -
Playing Unique Games on Certified Small-Set Expanders.
with Boaz Barak, Pravesh Kothari, Tselil Schramm and David Steurer
STOC 2021 -
Optimal Fine-grained Hardness of Approximation of Linear Equations.
with Nikhil Vyas
ICALP 2021 -
Local decoding and testing of polynomials over grids.
with Srikanth Srinivasan and Madhu Sudan
Random Structures and Algorithms (Journal) -
Imperfect Gaps in Gap-ETH and PCPs.
with Nikhil Vyas
CCC 2019 -
Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform.
with Jack Murtagh and Nikhil Vyas
NeurIPS 2018 -
The Price of Selection in Differential Privacy.
with Jonathan Ullman
COLT 2017 -
On the Sensitivity Conjecture for Read-k Formulas.
with Satyanarayana V. Lokam, Sébastien Tavenas and Ameya Velingker
MFCS 2016
Expositions
-
Elementary analysis of isolated zeroes of a polynomial system.
with Madhu Sudan, Santhoshini Velusamy and David Xiang -
An Exposition of Dinur-Khot-Kindler-Minzer-Safra’s Proof for the 2-to-2 Games Conjecture.
with Chi-Ning Chou and Zhao Song
Teaching
- Fall 2025: CSE 431 - Undergrad Complexity Theory, UW
- Spring 2025: 18.200 - Principles of Discrete Math, MIT (Recitation Leader, Instructor: Peter Shor)
- Fall 2024: 18.424 - Undergraduate Seminar in Information Theory, MIT
- Spring 2024: 18.200 - Principles of Discrete Math, MIT (Recitation Leader, Instructors: Peter Shor & Ankur Moitra)
- Fall 2023: 18.01 - Single Variable Calculus, MIT (Recitation Leader, Instructor: Prof. Larry Guth)
- Spring 2019: CS229r - Information Theory in Computer Science, Harvard (TA, Instructor: Prof. Madhu Sudan)
Service
- PC Member: STOC 2025
- Co-organized HDX Workshop at STOC 2025 (with Max Hopkins, Yotam Dikstein & Dor Minzer)