Publications and Preprints
New Approximation Bounds for Small-Set Vertex Expansion (SODA 2024) [arXiv]
Joint work with Anand Louis.
A PTAS for \ell_0-Low Rank Approximation : Solving Dense CSPs over Reals (SODA 2024) [arXiv]
Joint work with Vincent-Cohen Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay, Tony Chang Wang.
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs (FOCS 2023) [arXiv].
Joint work with Euiwoong Lee.
The Biased Homogeneous r-Lin Problem (APPROX 2022) [Conference] [arXiv version coming soon].
(Single Author).
Approximating CSPs with Outliers (APPROX 2022) [arXiv].
Joint work with Anand Louis.
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits (AISTATS 2022) [Conference]
Joint work with Aadirupa Saha.
A Characterization of Approximability for Biased CSPs (STOC 2022) [arXiv].
Joint work with Euiwoong Lee.
Hardness of learning DNFs using Halfspaces (STOC 2021) [arXiv].
Joint work with Rishi Saket.
Approximation Algorithms and Hardness for Strong Unique Games (SODA 2021) [arXiv].
Joint work with Anand Louis.
Tight Approximation Bounds for Maximum Multi-Coverage (IPCO 2020) [arXiv].
Joint work with Siddharth Barman, Omar Fawzi and Emirhan Gurpinar.
Combinatorial lower bounds for 3-query LDCs (ITCS 2020) [arXiv].
Joint work with Arnab Bhattacharyya and L. Sunil Chandran.
Approximation Algorithms for Partially Colorable Graphs (APPROX 2019) [Conference] [arXiv].
Joint work with Anand Louis and Rahul Raychaudhury.
Parameterized Intractibility of Even-Set and Shortest Vector Problem from Gap-ETH (ICALP 2018) [Conference] [arXiv]
Joint work with Arnab Bhattacharyya, Karthik C. S., and Pasin Manurangsi.
Hardness of Learning Noisy Halfspaces using Polynomial Thresholds (COLT 2018) [Conference] [arXiv].
Joint work with Arnab Bhattacharyya and Rishi Saket.
Testing Sparsity over Known and Unknown Bases (ICML 2018) [Conference] [arXiv].
Joint work with Siddharth Barman and Arnab Bhattacharyya.
On the Hardness of Learning Sparse Parities (ESA 2016) [Conference] [arXiv].
Joint work with Arnab Bhattacharyya, Ameet Gadekar, and Rishi Saket.