**Research Instructor **

**Department of Computer Science, Princeton University
Institute for Advanced Study, Princeton **

## Brief Bio

Before moving to Princeton, I received my PhD from UT Austin advised by Adam Klivans, where I was partially supported by the Simons Award for Graduate Students in Theoretical Computer Science, and Bachelor's degree from IIT Kanpur advised by Surender Baswana.

## Recent/Upcoming Events/Talks

ICERM Workshop on Real Algebraic Geometry and Optimization, Providence, RI [Oct'18]

IAS Computer Science and Discrete Mathematics Seminar, Princeton [Feb 6]

ITCS 2018, Cambridge, MA [Jan 11-14]

ICTS Workshop on Algorithms and Optimization, Bangalore, India [Jan'18]

MIT Theory of Computation Colloquium [Dec 5 2017]

Simons Workshop on Hierarchies, Extended Formulations and Matrix-Analytic Techniques, Berkeley, CA [Nov 2017]

Columbia Theory Seminar [Oct 27]

Guest Lecture: Seminar on New Directions in Theoretical Machine Learning, Princeton CS [Oct 2017]

FOCS 2017 [Oct 2017]

Oberwolfach Workshop on Proof Complexity and Beyond, Oberwolfach, Germany [Aug 2017]

## Contact

Email: "lastname" at cs dot princeton dot edu

Offices: Simonyi 007 (IAS, Default) and 413 (35, Olden Street, Princeton)

## Service

PC Member**APPROX/RANDOM 2018**

## Research

I am broadly interested in theoretical computer science.
My recent research has focused on investigating *meta-algorithms* such as the Sum of Squares method and Extended Formulations. Specifically, I have worked on

1) obtaining **fast algorithms** for problems arising in *unsupervised machine learning*, *combinatorial optimization*, *quantum information* and *cryptography* and, on the flip side,

2) obtaining general lower-bound techniques to gather evidence for tight **computational vs statistical complexity trade-offs** for some basic problems arising in average-case complexity.

## Selected Recent Papers (for all papers, see __here__)

Outlier-Robust Moment Estimation Via Sum-of-Squares

With David Steurer Show Abstract

** STOC 2018 (to appear) ** (conference version to be merged with the paper below)

Better Agnostic Clustering Via Relaxed Tensor Norms

With Jacob Steinhardt Show Abstract

** STOC 2018 (to appear) ** (conference version to be merged with the paper above)

Sum-of-Squares Meets Nash: Lower Bounds for finding * any * equilibrium

With Ruta Mehta Show Abstract

** STOC 2018 (to appear) **

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

With Boaz Barak , Zvika Brakerski and Ilan Komargodski

**EUROCRYPT 2018 (to appear) **
Show Abstract

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 **
Show Abstract

Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture

With Boaz Barak and David Steurer

**STOC, 2017 **
Show Abstract

Sum-of-Squares Lower Bounds for Refuting any CSP

With Ryuhei Mori , Ryan O'Donnell and David Witmer

**STOC, 2017 **
Show Abstract

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 *
Show Abstract

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. ** **[Video- IAS CS/DM Seminar] [Boaz's WOT post] **

* Invited to SICOMP Special Issue for FOCS 2016 *
Show Abstract

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 .) Show Abstract

Provable Submodular Minimization Using Wolfe's Algorithm

With Deeparnab Chakrabarty
and Prateek Jain

**NIPS 2014 (Oral Presentation) **
Show Abstract

## Preprints/Upcoming

SoS Lower Bounds with Hard Constraints: Think Global, Act Local

With Ryan O'Donnell and Tselil Schramm .
Show Abstract

Small-Set Expansion in Shortcode Graph and the 2-to-1 Conjecture

With Boaz Barak and David Steurer
Show Abstract

Efficient Algorithms for Outlier-Robust Regression

With Adam Klivans and Raghu Meka
Show Abstract

An Analysis of t-SNE Algorithm for Data Visualization

With Sanjeev Arora and Wei Hu
Show Abstract