Research Instructor
Department of Computer Science, Princeton University
Institute for Advanced Study, Princeton
Brief Bio
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.
In Fall 2019, I will join the Computer Science Department (and the diverse theory group) at CMU.
Venkatesan Guruswami and I are offering a joint postdoctoral fellowship starting Fall 2019 at the Computer Science Department, CMU. Check here for details.
Recent/Upcoming Events/Talks
University of Chicago Theory Seminar [Dec 2018]
Oberwolfach Workshop on Complexity Theory, Oberwolfach, Germany [Nov 2018]
ICERM Workshop on Real Algebraic Geometry and Optimization, Providence, RI [Oct'18]
Workshop on Analytic Techniques in Theoretical Computer Science, Oaxaca, Mexico [Aug 12-17]
TTI-Chicago Summer Workshop on High-Dimensional Robust Statistics [Aug 2018]
NYU Theory Seminar [May 2018]
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]
Oberwolfach Workshop on Proof Complexity and Beyond, Oberwolfach, Germany [Aug 2017]
Service
PC Member
APPROX/RANDOM 2018 ,
SODA 2019
Contact
Email: "lastname" at cs dot princeton dot edu
Offices: Simonyi 007 (IAS, Default) and 413 (35, Olden Street, Princeton)
Current Teaching
COS 597: Analytical Methods in Theoretical Computer Science
Course Webpage
Time/Venue : Mon-Wed 1:30:-2:50pm, Location: Friend 009 First Meeting: Feb 04.
Office Hours: Mon-Wed 3:00-4:00 pm (or by appointment)
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)
Small-Set Expansion in Shortcode Graph and the 2-to-1 Conjecture
With Boaz Barak and David Steurer
A generally accessible article on the recent proof of the 2-to-2 games conjecture that partly relies on this work.
Show Abstract
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain "Grassmanian agreement tester". In this work, we show that the hypothesis of Dinur et. al. follows from a conjecture we call the "Inverse Shortcode Hypothesis" characterizing the non-expanding sets of the degree-two shortcode graph. We also show the latter conjecture is equivalent to a characterization of the non-expanding sets in the Grassman graph, as hypothesized by a follow-up paper of Dinur et. al. (2017). Following our work, Khot, Minzer and Safra (2018) proved the "Inverse Shortcode Hypothesis". Combining their proof with our result and the reduction of Dinur et. al. (2016), completes the proof of the 2 to 2 conjecture with imperfect completeness. Moreover, we believe that the shortcode graph provides a useful view of both the hypothesis and the reduction, and might be useful in extending it further.
Efficient Algorithms for Outlier-Robust Regression
With Adam Klivans and Raghu Meka
COLT 2018 Show Abstract
An Analysis of t-SNE Algorithm for Data Visualization
With Sanjeev Arora and Wei Hu
COLT 2018
Show Abstract
Outlier-Robust Moment Estimation Via Sum-of-Squares
With David Steurer Show Abstract
We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in the recent works. We also show that the guarantees of our algorithms match information theoretic lower bounds for the class of distributions we consider. These improved guarantees allow us to give improved, outlier-robust algorithms for independent component analysis and learning mixtures of Gaussians.
Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem:
Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.
STOC 2018 (conference version to be merged with the paper below)
Better Agnostic Clustering Via Relaxed Tensor Norms
With Jacob Steinhardt Show Abstract
We develop a new scheme of convex relaxations for \( k \)-means clustering based on sum-of-squares
norms, a relaxation of the injective tensor norm that is efficiently computable using the
Sum-of-Squares algorithm. We give an algorithm based on this relaxation that recovers a
faithful approximation to the true means in the given data whenever the low-degree moments of
the points in each cluster have bounded in (sos relaxations of) injective tensor norms.
We then prove a sharp upper bound on the sum-of-squares relaxations of injective tensors norms for moment tensors of any distribution that satisfy the Poincare inequality . The Poincare inequality is intensely investigated
in probability theory, and a large class of random variables satisfy it including all rando variables with distributions that are arbitrary product or strongly log-concave including well-studied examples such as gaussians, and any sum or
continuous transformation of such distributions.
As an immediate corollary, for any \( \gamma > 0 \), we obtain an efficient algorithm for learning
the means of a mixture of \( k \) arbitrary Poincare distributions so long as the means have
dimension-independent separation \( \Omega(k^{\gamma}) \). This in particular yields an algorithm for learning spherical Gaussian
mixtures with dimension-independent separation \( \Omega(k^{\gamma}) \), thus partially resolving an open problem
recently posed by Regev and Vijayaraghavan (FOCS 2017).
Our algorithm further works even in the robust setting where an \( \varepsilon \) fraction of
arbitrary outliers are added to the data, as long as the fraction of outliers
is smaller than the smallest cluster. We therefore obtain results in the strong
agnostic setting where, in addition to not knowing the distribution family,
the data itself may be arbitrarily corrupted.
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 Show Abstract
STOC 2018
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)
With Boaz Barak , Zvika Brakerski and Ilan Komargodski
EUROCRYPT 2018
Show Abstract
An \( m \) output pseudorandom generator \( G\colon (\on^b)^n \rightarrow \on^m \) that takes input \( n \) blocks of \( b \) bits each is said to be \( \ell \)-block local if every output is a function of at most \( \ell \) blocks. We show that such \( \ell \)-block local pseudorandom generators can have output length at most \( \tilde{O}(2^{\ell b} n^{\lceil \ell/2 \rceil}) \), by presenting a polynomial time algorithm that distinguishes inputs of the form \( G(x) \) from inputs where each coordinate is sampled from the uniform distribution on \( m \) bits.
As a corollary, we refute some conjectures recently made in the context of constructing provably secure indistinguishability obfuscation (iO). This includes refuting the assumptions underlying Lin and
Tessaro's (2017) recently proposed candidate iO from bilinear maps. Specifically, they
assumed the existence of a secure pseudorandom generator \( G:\colon \{ \pm 1 \}^{nb} \rightarrow \on^{2^{cb}n} \) as above for large enough \( c>3 \) and \( \ell=2 \).
(Following this work, and an independent work of Lombardi and Vaikuntanthan (2017),
Lin and Tessaro retracted the bilinear maps based candidate from their manuscript.)
Our results actually hold for the much wider class of low-degree, non-binary valued pseudorandom generators: if every output of \( G\colon\pmset^n \rightarrow \R^m \) (\( \mathbb{R} \) = reals) is a polynomial (over \( \mathbb{R} \)) of degree at most \( d \) with at most \( s \)
monomials and \( m \ge \tilde{\Omega}(sn^{\lceil d/2 \rceil}) \), then there is a
polynomial time algorithm for distinguishing the output \( G(x) \) from \( z \) where each coordinate \( z_i \) is sampled independently from the marginal distribution on \( G_i \). Furthermore, our results continue to hold under arbitrary pre-processing of the seed. This implies that any such map \( G \), with arbitrary seed pre-processing, cannot be a pseudorandom generator in the mild sense of fooling a product distribution on the output space. This allows us to rule out various natural modifications to the notion of generators suggested in other works that still allow obtaining indistinguishability obfuscation from bilinear maps.
Our algorithms are based on the Sum of Squares (SoS) paradigm, and in most cases can even be defined more simply using a canonical semidefinite program.
We complement our algorithm by presenting a class of candidate generators with
block-wise locality \( 3 \) and constant block size, that resists both Gaussian
elimination and sum of squares (SOS) algorithms whenever \( m = n^{1.5-\epsilon} \). This class is
extremely easy to describe: Let \( \mathbb{G} \) be any simple non-abelian group with
the group operation ``\( \ast \)'', and interpret the blocks of \( x \) as elements in
\( \mathbb{G} \). The description of the pseudorandom generator is a sequence of \( m \)
triples of indices \( (i,j,k) \) chosen at random and each output of the generator
is of the form \( x_i \ast x_j \ast x_k \).
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
We study planted problems---finding hidden structures in random noisy inputs---through the lens of the sum-of-squares semidefinite programming hierarchy (SoS).
This family of powerful semidefinite programs has recently yielded many new algorithms for planted problems, often achieving the best known polynomial-time guarantees in terms of accuracy of recovered solutions and robustness to noise.
One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems.
Classical spectral algorithms are often unable to accomplish this: the twist in these new spectral algorithms is the use of spectral structure of matrices whose entries are low-degree polynomials of the input variables.
We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-\( k \)-subgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-$d$ matrix polynomials are as powerful as SoS semidefinite programs of size roughly \( n^d \).
For such problems it is therefore always possible to match the guarantees of \sos without solving a large semidefinite program.
Using related ideas on \sos algorithms and low-degree matrix polynomials (and inspired by recent work on SoS and the planted clique problem (Barak-Hopkins-Kelner-Kothari-Moitra-Potechin 2016), we prove new nearly-tight SoS lower bounds for the tensor and sparse principal component analysis problems.
Our lower bounds are the first to suggest that improving upon the signal-to-noise ratios handled by existing polynomial-time algorithms for these problems may require subexponential time.
Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture
With Boaz Barak and David Steurer
STOC, 2017
Show Abstract
For every \( \epsilon>0 \), we give an \( \exp(\tilde{O}(\sqrt{n}/\epsilon^2)) \)-time algorithm for the \( 1 \) vs \( 1-\epsilon \) Best Separable State (BSS) problem of distinguishing,
given an \( n^2\times n^2 \) matrix \( \cM \) corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state \( \rho \) that \( \cM \) accepts with probability \( 1 \), and the case that every separable state is accepted with probability at most \( 1-\epsilon \).
Equivalently, our algorithm takes the description of a subspace \( \mathcal{W} \subseteq \mathbb F^{n^2} \) (where \( \mathbb F \) can be either the real or complex field) and distinguishes between the case that \( \mathcal{W} \) contains a rank one matrix, and the case that every rank one matrix is at least \( \epsilon \) far (in \( \ell_2 \) distance) from \( \mathcal{W} \).
To the best of our knowledge, this is the first improvement over the brute-force \( \exp(n) \)-time algorithm for this problem.
Our algorithm is based on the Sum-of-Squares hierarchy and its analysis is inspired by Lovett's proof (STOC '14, JACM '16) that the communication complexity of every rank-\( n \) Boolean matrix is bounded by \( \tilde{O}(\sqrt{n}) \).
Sum-of-Squares Lower Bounds for Refuting any CSP
With Ryuhei Mori , Ryan O'Donnell and David Witmer
STOC, 2017
Show Abstract
Let \( P:\{0,1\}^k \to \{0,1\} \) be a nontrivial \( k \)-ary predicate. Consider a random instance of the constraint satisfaction problem \( CSP(P) \) on \( n \) variables with \( \Delta n \) constraints, each being \( P \) applied to \( k \) randomly chosen literals. Provided the constraint density satisfies \( \Delta \gg 1 \), such an instance is unsatisfiable with high probability. The refutation problem asks to efficiently find a proof of unsatisfiability.
We show that whenever the predicate \( P \) supports a \( t \)- wise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree \( d = \Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta}) \) (which runs in time \( n^{O(d)} \) cannot refute a random instance of \( CSP(P) \). In particular, the polynomial-time SOS algorithm requires \( \tilde{\Omega}(n^{(t+1)/2}) \) constraints to refute random instances of CSP(P) when \( P \) supports a \( t \)-wise uniform distribution on its satisfying assignments.
More generally, we consider the \( \delta \)-refutation problem, in which the goal is to certify that at most a \( (1-\delta) \)-fraction of constraints can be simultaneously satisfied. We show that if \( P \) is \( \delta \)-close to supporting a \( t \)-wise uniform distribution on satisfying assignments, then the degree-\( \Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta}) \) SOS algorithm cannot \( (\delta+o(1)) \)-refute a random instance of CSP(P). This is the first result to show a distinction between the degree SOS needs to solve the refutation problem and the degree it needs to solve the harder \( \delta \)-refutation problem.
Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate \(P\), they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen-O'Donnell-Witmer (STOC 2015) and Raghavendra-Rao-Schramm (STOC 2016), this full three-way tradeoff is tight , up to lower-order factors.
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
We show that for constraint satisfaction problems (CSPs), weakly-exponential size linear programming relaxations are as powerful as \( n^{\Omega(1)} \)-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results; previously, it was only known that linear programs of size \( n^{o(\log n)}\) cannot beat random guessing for any CSP (Chan-Lee-Raghavendra-Steurer 2013).
Our bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The main ingredient in our results is a new structural result on ``high-entropy rectangles'' that may of independent interest in communication complexity.
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
We prove that with high probability over the choice of a random graph \( G\) from the Erdős–Rényi distribution \( G(n,1/2) \), the \( n^{O(d)} \)-time degree \( d \) Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least \( n^{1/2-c(d/\log n)^{1/2}} \) for some constant \( c>0 \).
This yields a nearly tight \( n^{1/2 - o(1)} \) bound on the value of this program for any degree \( d = o(\log n) \). Moreover, we introduce a new framework that we call pseudo-calibration to construct Sum-of-Squares lower bounds.
This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.
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
The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size \( \omega \gg \log{(n)} \) added to an Erdős–Rényi graph \( G \sim G(n,1/2) \), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size \( \omega = \tilde{\Omega}(n^{1/2}) \). By contrast, information theoretically, one can recover planted cliques so long as \( \omega \gg \log{(n)} \). In this work, we continue the investigation of algorithms from the sum of squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson (MPW, 2015) and Deshpande and Montanari (DM,2015). Our main results improve upon both these previous works by showing:
1. Degree four SoS does not recover the planted clique unless \( \omega \gg n^{1/2}/ poly \log{(n)} \), improving upon the bound \( \omega \gg n^{1/3} \) due to DM. A similar result was obtained independently by Raghavendra and Schramm (2015).
2. For \( 2 < d = o(\sqrt{log{(n)}}) \), degree 2d SoS does not recover the planted clique unless \( \omega \gg n^{\frac{1}{d+1}}/2^d poly \log{(n)} \), improving upon the bound due to MPW.
Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works MPW,DM and Feige and Krauthgamer (2003) by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev (2001).
An argument of Kelner shows that the first result cannot be proved using the same certificate. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by "correcting" the certificate of previous works.
Provable Submodular Minimization Using Wolfe's Algorithm
With Deeparnab Chakrabarty
and Prateek Jain
NIPS 2014 (Oral Presentation)
Show Abstract
Owing to several applications in large scale learning and vision problems, fast submodular function minimization (SFM) has become a critical problem. Theoretically, unconstrained SFM can be performed in polynomial time [Iwata-Fujishige-Fleisher 2001, Iwata-Orlin 2009]. However, these algorithms are typically not practical. In 1976, Wolfe proposed an algorithm to find the minimum Euclidean norm point in a polytope, and in 1980, Fujishige showed how Wolfe's algorithm can be used for SFM. For general submodular functions, this Fujishige-Wolfe minimum norm algorithm seems to have the best empirical performance.
Despite its good practical performance, very little is known about Wolfe's minimum norm algorithm theoretically. To our knowledge, the only result is an exponential time analysis due to Wolfe himself. In this paper we give a maiden convergence analysis of Wolfe's algorithm. We prove that in \( t \) iterations, Wolfe's algorithm returns an \( O(1/t) \)-approximate solution to the min-norm point on any polytope. We also prove a robust version of Fujishige's theorem which shows that an \( O(1/n^2)\) -approximate solution to the min-norm point on the base polytope implies exact submodular minimization. As a corollary, we get the first pseudo-polynomial time guarantee for the Fujishige-Wolfe minimum norm algorithm for unconstrained submodular function minimization.