**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]

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

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)

## Research

I am broadly interested in theoretical computer science.
Currently, a major focus in my research is to understand the power of the sum-of-squares method in the context of 1) **algorithm design ** - in order to obtain fast approximation algorithms for problems in Machine Learning, Combinatorial Optimization and beyond and 2) ** average case complexity ** - in order to gather evidence of hardness and computational vs statistical complexity tradeoffs for solving *random/typical* instances of hard optimization problems.

## Preprints/Upcoming

Outlier-Robust Moment Estimation Via Sum-of-Squares

With David Steurer
Show Abstract

Better Agnostic Clustering Via Relaxed Tensor Norms

With Jacob Steinhardt Show Abstract

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

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

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

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

With Boaz Barak , Zvika Brakerski and Ilan Komargodski

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