Manuscript(s)
 An Exponential Lower Bound on Linear ThreeQuery 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).  PublicKey Encryption, Local Pseudorandom Generators, and the
LowDegree 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 MaxCut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
With Tim Hsieh
ICALP, 2023.  A NearCubic Lower Bound for 3Query 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 semirandom planted clique
With Rares Buhai and David Steurer
STOC, 2023.  A MomentMatching 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.  PolynomialTime PowerSum 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  Listdecodable 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.
 PolynomialTime SumofSquares 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.  MemorySample Lower Bounds for Learning Parity with Noise
With Sumegha Garg, Pengda Liu, and Ran Raz.
RANDOM, 2021.
 A StressFree SumofSquares Lower Bound for Coloring
With Peter Manohar.
CCC, 2021.
 Playing Unique Games on Certified SmallSet Expanders
With Mitali Bafna , Boaz Barak , Tselil Schramm and David Steurer.
STOC, 2021.

Strongly refuting all semirandom Boolean CSPs
With Jackson Abascal and Venkat Guruswami .
SODA, 2021.
 ListDecodable Subspace Recovery: Dimension Independent Error in Polynomial Time
With Ainesh Bakshi
SODA, 2021.
 OutlierRobust Clustering of NonSpherical 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.  TimeSpace Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
With Sumegha Garg and Ran Raz
RANDOM, 2020.
 ListDecodable 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  SumofSquares 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 .

SmallSet Expansion in Shortcode Graph and the 2to1 Conjecture
With Boaz Barak and David Steurer
ITCS 2019 . 
Efficient Algorithms for OutlierRobust Regression
With Adam Klivans and Raghu Meka
COLT 2018. 
An Analysis of tSNE Algorithm for Data Visualization
With Sanjeev Arora and Wei Hu
COLT 2018. 
OutlierRobust Moment Estimation Via SumofSquares
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)
 SumofSquares Meets Nash: Lower Bounds for finding any equilibrium
With Ruta Mehta
STOC 2018

Agnostic Learning by Refuting
With Roi Livni
ITCS 2018 . 
Limits on LowDegree Pseudorandom Generators (Or: SumofSquares Meets Program Obfuscation)
With Boaz Barak , Zvika Brakerski and Ilan Komargodski
EUROCRYPT 2018. 
The power of sumofsquares for detecting hidden structures
With Samuel B. Hopkins , Aaron Potechin , Prasad Raghavendra , Tselil Schramm and David Steurer
FOCS 2017. 
Quantum Entanglement, SumofSquares and the LogRank 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 
SumofSquares Lower Bounds for Refuting any CSP
With Ryuhei Mori , Ryan O'Donnell and David Witmer
STOC, 2017. 
A Nearly Tight SumofSquares 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 Degree4 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 Lowrank 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 VCTheorem for LowDegree 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.