Manuscript(s)

• An Exponential Lower Bound on Linear Three-Query Locally Correctable Codes
  With Peter Manohar
  Manuscript, 2023
  

Published Papers

• New SDP Roundings and Certifiable Approximation for Cubic Optimization
  With Tim Hsieh, Lucas Pesenti, and Luca Trevisan
  SODA, 2023 (to appear).
• Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method
  With Andrej Bogdanov and Alon Rosen
  TCC, 2023 (to appear).
• Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
  With Venkat Guruswami , Tim Hsieh, and Peter Manohar
  FOCS, 2023 (to appear).
• Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
  With He Jia and Santosh Vempala
  FOCS, 2023 (to appear).
• Is Planted Coloring Easier than Planted Clique?
  With Santosh Vempala, Alex Wein , and Jeff Xu
  COLT, 2023.
• Ellipsoid Fitting Up to a Constant
  With Tim Hsieh, Aaron Potechin, and Jeff Xu
  ICALP, 2023.
• Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
  With Tim Hsieh
  ICALP, 2023.
• A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
  With Omar Alrabiah, Venkat Guruswami and Peter Manohar
  STOC, 2023.
  Invited to SICOMP Special Issue for STOC'23
• Algorithms approaching the threshold for semi-random planted clique
  With Rares Buhai and David Steurer
  STOC, 2023.
• A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
  With Aravind Gallakota and Adam Klivans
  STOC, 2023.
  Invited to SICOMP Special Issue for STOC'23
• Privately Estimating a Gaussian: Efficient, Robust and Optimal
  With Daniel Alabi, Pranay Tankala, Prayaag Venkat and Fred Zhang
  STOC, 2023.
• A simple and sharper proof of the hypergraph Moore bound
  With Tim Hsieh and Sidhanth Mohanty
  SODA, 2023.
• Polynomial-Time Power-Sum Decomposition of Polynomials
  With Mitali Bafna, Tim Hsieh, and Jeff Xu
  FOCS 2022.
• Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number
  With Venkat Guruswami and Peter Manohar
  APPROX, 2022.
  
• Private Robust Estimation by Stabilizing Convex Relaxations
  With Pasin Manurangsi and Ameya Velingker.
  COLT, 2022
• List-decodable Covariance Estimation
  With Misha Ivkov
  STOC, 2022
• Algorithms and Certificates for Boolean CSP Refutation: Smoothed is no Harder than Random
  With Venkat Guruswami and Peter Manohar
  STOC, 2022.
  Invited to SICOMP Special Issue for STOC 2022
• Robustly Learning a Mixture of $k$ Arbitrary Gaussians
  With Ainesh Bakshi , Ilias Diakonikolas, He Jia, Daniel Kane, Santosh Vempala
  STOC, 2022.
  
• Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
  With Peter Manohar and Brian Zhang
  ALT, 2022
• Algorithmic Thresholds for Refuting Random Polynomial Systems
  With Tim Hsieh.
  SODA, 2022.
• Memory-Sample Lower Bounds for Learning Parity with Noise
  With Sumegha Garg, Pengda Liu, and Ran Raz.
  RANDOM, 2021.
  
• A Stress-Free Sum-of-Squares Lower Bound for Coloring
  With Peter Manohar.
  CCC, 2021.
  
• Playing Unique Games on Certified Small-Set Expanders
  With Mitali Bafna , Boaz Barak , Tselil Schramm and David Steurer.
  STOC, 2021.
  
• Strongly refuting all semi-random Boolean CSPs
  With Jackson Abascal and Venkat Guruswami .
  SODA, 2021.
  
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time
  With Ainesh Bakshi
  SODA, 2021.
  
• Outlier-Robust Clustering of Non-Spherical Mixtures
  With Ainesh Bakshi
  FOCS, 2020.
  Conference version to be merged with this paper.
• Sparse PCA: algorithms, adversarial perturbations and certificates
  With Tommaso D'Orsi, Gleb Novikov, and David Steurer .
  FOCS 2020.
• Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
  With Sumegha Garg and Ran Raz
  RANDOM, 2020.
  
• List-Decodable Linear Regression
  With Sushrut Karmalkar and Adam Klivans
  NeuIPS Spotlight, 2019.
  
• Kernel Learning Via Association Schemes
  With Roi Livni
  ALT 2020
  
• Approximation Schemes for a Buyer with Independent Items via Symmetries
  With Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, and S. Matthew Weinberg
  FOCS 2019.
  Invited to the Highlights of Algorithms (HALG) 2020
• Sum-of-Squares Meets Program Obfuscation, Revisited
  With Boaz Barak , Samuel B. Hopkins , Aayush Jain and Amit Sahai
  EUROCRYPT 2019 .
  
• SoS Lower Bounds for Hard Constraints: Think Global, Act Local
  With Ryan O'Donnell and Tselil Schramm .
  ITCS 2019 .
  
• Small-Set Expansion in Shortcode Graph and the 2-to-1 Conjecture
  With Boaz Barak and David Steurer
  ITCS 2019 .
• Efficient Algorithms for Outlier-Robust Regression
  With Adam Klivans and Raghu Meka
  COLT 2018.
• An Analysis of t-SNE Algorithm for Data Visualization
  With Sanjeev Arora and Wei Hu
  COLT 2018.
• Outlier-Robust Moment Estimation Via Sum-of-Squares
  With David Steurer
  STOC 2018 (conference version to be merged with the paper below)
  
• Better Agnostic Clustering Via Relaxed Tensor Norms
  With Jacob Steinhardt
  STOC 2018 (conference version to be merged with the paper above)
  
• Sum-of-Squares Meets Nash: Lower Bounds for finding any equilibrium
  With Ruta Mehta
  STOC 2018
  
• Agnostic Learning by Refuting
  With Roi Livni
  ITCS 2018 .
• Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)
  With Boaz Barak , Zvika Brakerski and Ilan Komargodski
  EUROCRYPT 2018.
• The power of sum-of-squares for detecting hidden structures
  With Samuel B. Hopkins , Aaron Potechin , Prasad Raghavendra , Tselil Schramm and David Steurer
  FOCS 2017.
• Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture
  With Boaz Barak and David Steurer)
  STOC 2017.
• Approximating Rectangles by Juntas and a Weakly Exponential Lower Bound for LP Relaxations of CSPs
  With Raghu Meka and Prasad Raghavendra
  STOC 2017.
  Invited to SICOMP Special Issue for STOC 2017
• Sum-of-Squares Lower Bounds for Refuting any CSP
  With Ryuhei Mori , Ryan O'Donnell and David Witmer
  STOC, 2017.
• A Nearly Tight Sum-of-Squares Lower Bound for Planted Clique
  With Boaz Barak , Sam Hopkins , Jon Kelner , Ankur Moitra and Aaron Potechin
  FOCS 2016.
  Invited to SICOMP Special Issue for FOCS 2016
  [Video- IAS CS/DM Seminar] [Boaz's WOT post]
• SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four
  With Samuel B. Hopkins and Aaron Potechin
  SODA 2016.
  Invited to the ACM Transactions on Algorithms, Special Issue for SODA 2016
  (Conference version to be merged with Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program by Tselil Schramm and Prasad Raghavendra .)
• Communication with Contextual Uncertainty
  With Badih Ghazi , Ilan Komargodski and Madhu Sudan
  SODA 2016.
• Sum of Squares Lower Bounds from Pairwise Independence
  With Boaz Barak and Siu On Chan
  STOC 2015.
• Almost Optimal Pseudorandom Generators for Spherical Caps
  With Raghu Meka
  STOC 2015.
• Agnostic Learning of Disjunctions on Symmetric Distributions
  With Vitaly Feldman
  JMLR 2015
• Provable Submodular Minimization Using Wolfe's Algorithm
  With Deeparnab Chakrabarty and Prateek Jain
  NIPS 2014 (Oral Presentation)
• Embedding Hard Learning Problems in Gaussian Space
  With Adam Klivans
  RANDOM 2014.
• Nearly Tight Bounds for L_1 Approximating Self Bounding Functions
  With Vitaly Feldman, Jan Vondrak
  ALT 2017.
• Testing Surface Area
  With Ryan O'Donnell, Amir Nayerri and Chengang Wu
  SODA 2014.
• Learning Coverage Functions and Private Release of Marginals
  With Vitaly Feldman
  COLT 2014.
• Representation, Approximation and Learning
  of Submodular Functions Using Low-rank Decision Trees
  With Vitaly Feldman and Jan Vondrak
  COLT 2013.
• Constructing Hard Functions from Learning Algorithms
  With Adam Klivans and Igor C. Oliveira
  CCC 2013.
• An Explicit VC-Theorem for Low-Degree Polynomials
  With Eshan Chattopadhyay and Adam Klivans
  RANDOM 2012.
• Differentially Private Online Learning
  (with Prateek Jain and Abhradeep Guha Thakurta)
  COLT 2012.
• Submodular Functions are Noise Stable
  With Adam Klivans, Homin K Lee and Mahdi Cheraghchi
  SODA 2012.
• A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs
  With Madan Musuvathi, Sebastian Burckhardt and Santosh Nagarakatte
  ASPLOS 2010.