Preprints

Kernel Learning Via Association Schemes
With Roi Livni
2017.
Published Papers
 SumofSquares Meets Program Obfuscation, Revisited
With Boaz Barak , Samuel B. Hopkins , Aayush Jain and Amit Sahai
EUROCRYPT 2019 (to appear) .
 SoS Lower Bounds for Hard Constraints: Think Global, Act Local
With Ryan O'Donnell and Tselil Schramm .
ITCS 2019 (to appear) .

SmallSet Expansion in Shortcode Graph and the 2to1 Conjecture
With Boaz Barak and David Steurer
ITCS 2019 (to appear).

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)

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.

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.

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.