Aravindan Vijayaraghavan

I am an Associate Professor in the CS department at Northwestern University, and by courtesy, the IEMS department. I'm a member of the Theory CS Group and my research interests are broadly in theoretical computer science. I work on the algorithmic foundations of machine learning, data science, combinatorial optimization, and more recently, quantum information. I am particularly interested in using paradigms that go Beyond Worst-Case Analysis to obtain good algorithmic guarantees.

I also serve as a Site Director (Northwestern) of the Institute for Data, Economics, Algorithms and Learning (IDEAL), and served as the Institute Director in 2023-24. IDEAL is an NSF-funded collaborative institute across Northwestern, TTI Chicago, UIC, U of Chicago, and IIT. My research was also supported by an NSF CAREER award, an NSF AITF award CCF-1637585 (with David Sontag), CCF-2154100 (with Julia Gaudio) and the Google Research Scholar program .

Prior to joining Northwestern in Fall 2015, I was at Courant, NYU for a year as a part of the Simons Collaboration on Algorithms and Geometry , and was a Simons Postdoctoral Research Fellow with the Theory Group at Carnegie Mellon University. I obtained my PhD from Princeton University in Computer Science with Prof. Moses Charikar. Prior to that, I finished my bachelor's degree in CS from the Indian Institute of Technology Madras in 2007. I spent the first fifteen years of my life in Pondicherry, a beautiful town in Southern India, where Pi Patel hails from.

Teaching

CS262: Mathematical Foundations of CS Part 2- Continuous Mathematics for Computer Science. Spring 2024, Spring 2025.
CS212: Mathematical Foundations of Computer Science. Fall 2015, 2016, 2017, Spring 2019, Fall 2019, Winter 2021, Fall 2022.
CS496: Graduate Algorithms. Winter 2016, 2017, Spring 2018, Winter 2019, Winter 2022.
CS 396/496: Foundations of Quantum Computation & Quantum Information Winter 2022 (co-taught with S. Rao), Winter 2024, Fall 2024
CS 335: Intro to the Theory of Computation (co-taught with Jason Hartline) Fall 2020, Spring 2022.
CS 496: Foundations of Reliable Machine Learning Fall 2021, Fall 2023.
CS 497: Recent Highlights in Theoretical CS Winter 2022.
CS496: Theoretical Foundations of Data Science Spring 2021.
CS496/ ECE495: Algorithmic Aspects of Network Inference Spring 2020 (co-taught with R. Berry).
CS496: Topics in Theoretical Machine Learning. Winter 2018.
CS 496 : Beyond Worst-Case Analysis. Spring 2017.

Students

PhD students: Abhratanu Dutta (defended in 2020; first job: Facebook research), Aidao Chen (defended in 2023; first job: Accutar Biotech. Co-advised with Anindya De) Aravind Reddy (defended in 2023; Broad institute. Co-advised with Konstantin Makarychev), Sanchit Kalhan (co-advised with Konstantin Makarychev), Alex Tang (defended in 2024),
Vaidehi Srinivas , Anxin (Bob) Guo , Dionysios Arvanitakis (co-advised with Konstantin Makarychev).
Postdocs (co)-mentored: Xue Chen (first job: Assistant Professor, George Mason University, CS), Shravas Rao (first job: Assistant Professor, Portland State University, CS), Jinshuo Dong (first job: Assistant Professor, Peking University, Yau Institute of Mathematical Sciences), Eric Evert (first job: University of Florida, Math), He Jia .
Prospective Students: If you are a bright and motivated student interested in theoretical computer science, I encourage you to apply to the PhD program at Northwestern University. See here for details.

Professional Activities and Theory Events

FOCS 2024: General Chair.
Quarterly Theory Workshop and Junior Theory Workshop series: Co-organizer.
Program Committees/ Senior Area Chairs/ Area Chairs (or equivalent): ICML 2025, COLT 2024, ALT 2024, ICML 2024, FOCS 2023, ICML 2023, COLT 2023, ALT 2023, NeurIPS 2022, COLT 2022, ALT 2022, STOC 2021, COLT 2021, WADS 2021, COLT 2020, ESA 2019, COLT 2019, APPROX 2018, SODA 2015
See IDEAL for details about IDEAL events and seminars.

Book Chapters or Surveys

Efficient Tensor Decomposition. [ArXiv| Book Link | Abstract]
This chapter studies the problem of decomposing a tensor into a sum of constituent rank one tensors. While tensor decompositions are very useful in designing learning algorithms and data analysis, they are NP-hard in the worst-case. We will see how to design efficient algorithms with provable guarantees under mild assumptions, and using beyond worst-case frameworks like smoothed analysis.

Book Chapter in Beyond the Worst Case Analysis of Algorithms
Edited by Tim Roughgarden, Cambridge University Press 2020.

Publications

Theoretical Analysis of Weak-to-Strong Generalization NeurIPS 2024.
(With Hunter Lang, David Sontag). [ArXiv| Abstract]

Strong student models can learn from weaker teachers: when trained on the predictions of a weaker model, a strong pretrained student can learn to correct the weak model's errors and generalize to examples where the teacher is not confident, even when these examples are excluded from training. This enables learning from cheap, incomplete, and possibly incorrect label information, such as coarse logical rules or the generations of a language model. We show that existing weak supervision theory fails to account for both of these effects, which we call pseudolabel correction and coverage expansion, respectively. We give a new bound based on expansion properties of the data distribution and student hypothesis class that directly accounts for pseudolabel correction and coverage expansion. Our bounds capture the intuition that weak-to-strong generalization occurs when the strong model is unable to fit the mistakes of the weak teacher without incurring additional error. We show that these expansion properties can be checked from finite data and give empirical evidence that they hold in practice.
Efficient Certificates of Anti-Concentration Beyond Gaussians FOCS 2024.
(With Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran and Madhur Tulsiani). [ArXiv| Abstract]

A set of high dimensional points X={x1,x2,…,xn}⊂Rd in isotropic position is said to be δ-anti concentrated if for every direction v, the fraction of points in X satisfying |⟨xi,v⟩|≤δ is at most O(δ). Motivated by applications to list-decodable learning and clustering, recent works have considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points X corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures, yet remain limited to rotationally invariant distributions. This work presents a new (and arguably the most natural) formulation for anti-concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over Lp balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to such distributions. Our approach constructs a canonical integer program for anti-concentration and analysis a sum-of-squares relaxation of it, independent of the intended application. We rely on duality and analyze a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions.
New tools for smoothed analysis: least singular values for random matrices with dependent entries STOC 2024. (With Aditya Bhaskara, Eric Evert and Vaidehi Srinivas). [ArXiv| Abstract]

We develop new techniques for proving lower bounds on the least singular value of random matrices with limited randomness. The matrices we consider have entries that are given by polynomials of a few underlying base random variables. This setting captures a core technical challenge for obtaining smoothed analysis guarantees in many algorithmic settings. Least singular value bounds often involve showing strong anti-concentration inequalities that are intricate and much less understood compared to concentration (or large deviation) bounds. First, we introduce a general technique for proving anti-concentration that uses well-conditionedness properties of the Jacobian of a polynomial map, and show how to combine this with a hierarchical $\epsilon$-net argument to prove least singular value bounds. Our second tool is a new statement about least singular values to reason about higher-order lifts of smoothed matrices and the action of linear operators on them. Apart from getting simpler proofs of existing smoothed analysis results, we use these tools to now handle more general families of random matrices. This allows us to produce smoothed analysis guarantees in several previously open settings. These new settings include smoothed analysis guarantees for power sum decompositions and certifying robust entanglement of subspaces, where prior work could only establish least singular value bounds for fully random instances or only show non-robust genericity guarantees.
Error tolerant e-Discovery protocols CSLAW 2024.
(With Jinshuo Dong, Jason Hartline and Liren Shan). [ArXiv| Abstract]
We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) in the context of electronic discovery (e-discovery). Based on a request for production from the requesting party, the responding party is required to provide documents that are responsive to the request except for those that are legally privileged. Our goal is to find a protocol that verifies that the responding party sends almost all responsive documents while minimizing the disclosure of non-responsive documents. We provide protocols in the challenging non-realizable setting, where the instance may not be perfectly separated by a linear classifier. We demonstrate empirically that our protocol successfully manages to find almost all relevant documents, while incurring only a small disclosure of non-responsive documents. We complement this with a theoretical analysis of our protocol in the single-dimensional setting, and other experiments on simulated data which suggest that the non-responsive disclosure incurred by our protocol may be unavoidable.
Higher-order Cheeger Inequality for Partitioning with Buffers SODA 2024.
(With Konstantin Makarychev, Yury Makarychev and Liren Shan). [ ArXiv | Abstract]
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond FOCS 2023. (With Nathaniel Johnston and Benjamin Lovitz). [ArXiv| Abstract]

We study the problem of finding elements in the intersection of an arbitrary conic variety in $\mathbb{F}^n$ with a given linear subspace (where $\mathbb{F}$ can be the real or complex field). This problem captures a rich family of algorithmic problems under different choices of the variety. The special case of the variety consisting of rank-1 matrices already has strong connections to central problems in different areas like quantum information theory and tensor decompositions. This problem is known to be NP-hard in the worst-case, even for the variety of rank-1 matrices. Surprisingly, despite these hardness results we give efficient algorithms that solve this problem for "typical" subspaces. Here, the subspace $U \subset \mathbb{F}^n$ is chosen generically of a certain dimension, potentially with some generic elements of the variety contained in it. Our main algorithmic result is a polynomial time algorithm that recovers all the elements of $U$ that lie in the variety, under some mild non-degeneracy assumptions on the variety. As corollaries, we obtain the following results: - Uniqueness results and polynomial time algorithms for generic instances of a broad class of low-rank decomposition problems that go beyond tensor decompositions. Here, we recover a decomposition of the form $\sum_i v_i \otimes w_i$, where the $v_i$ are elements of the given variety $X$. This implies new algorithmic results even in the special case of tensor decompositions. - Polynomial time algorithms for several entangled subspaces problems in quantum entanglement, including determining r-entanglement, complete entanglement, and genuine entanglement of a subspace. While all of these problems are NP-hard in the worst case, our algorithm solves them in polynomial time for generic subspaces of dimension up to a constant multiple of the maximum possible.
A Complete Hierarchy of Linear Systems for Certifying Quantum Entanglement of Subspaces QIP 2023, Physical Review A (journal). (With Nathaniel Johnston and Benjamin Lovitz). [ArXiv| Abstract]

We introduce a hierarchy of linear systems for showing that a given subspace of pure quantum states is entangled (i.e., contains no product states). This hierarchy outperforms known methods already at the first level, and it is complete in the sense that every entangled subspace is shown to be so at some finite level of the hierarchy. It generalizes straightforwardly to the case of higher Schmidt rank, as well as the multipartite cases of completely and genuinely entangled subspaces. These hierarchies work extremely well in practice even in very large quantum systems, as they can be implemented via elementary linear algebra techniques rather than the semidefinite programming techniques that are required by previously-known hierarchies.
Agnostic Learning of General ReLU Activation Using Gradient Descent ICLR 2023
(With Pranjal Awasthi and Alex Tang). [ArXiv| Abstract]

We provide a convergence analysis of gradient descent for the problem of agnostically learning a single ReLU function under Gaussian distributions. Unlike prior work that studies the setting of zero bias, we consider the more challenging scenario when the bias of the ReLU function is non-zero. Our main result establishes that starting from random initialization, in a polynomial number of iterations gradient descent outputs, with high probability, a ReLU function that achieves a competitive error guarantee when compared to the error of the best ReLU function. We also provide finite sample guarantees, and these techniques generalize to a broader class of marginal distributions beyond Gaussians.
The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound NeurIPS 2022.
(With Liam O'Carroll and Vaidehi Srinivas). [ArXiv| Abstract]

The most widely used technique for solving large-scale semidefinite programs (SDPs) in practice is the non-convex Burer-Monteiro method, which explicitly maintains a low-rank SDP solution for memory efficiency. There has been much recent interest in obtaining a better theoretical understanding of the Burer-Monteiro method. When the maximum allowed rank p of the SDP solution is above the Barvinok-Pataki bound (where a globally optimal solution of rank at most $p$ is guaranteed to exist), a recent line of work established convergence to a global optimum for generic or smoothed instances of the problem. However, it was open whether there even exists an instance in this regime where the Burer-Monteiro method fails. We prove that the Burer-Monteiro method can fail for the Max-Cut SDP on n vertices when the rank is above the Barvinok-Pataki bound ($p \ge \sqrt{2n}$). We provide a family of instances that have spurious local minima even when the rank $p=n/2$. Combined with existing guarantees, this settles the question of the existence of spurious local minima for the Max-Cut formulation in all ranges of the rank and justifies the use of beyond worst-case paradigms like smoothed analysis to obtain guarantees for the Burer-Monteiro method.
Training subset selection for Weak Supervision NeurIPS 2022.
Hunter Lang, Aravindan Vijayaraghavan and David Sontag (non-alphabetical ordering). [ArXiv| Abstract]

Existing weak supervision approaches use all the data covered by weak signals to train a classifier. We show both theoretically and empirically that this is not always optimal. Intuitively, there is a tradeoff between the amount of weakly-labeled data and the precision of the weak labels. We explore this tradeoff by combining pretrained data representations with the cut statistic (Muhlenbach et al., 2004) to select (hopefully) high-quality subsets of the weakly-labeled training data. Subset selection applies to any label model and classifier and is very simple to plug in to existing weak supervision pipelines, requiring just a few lines of code. We show our subset selection method improves the performance of weak supervision for a wide range of label models, classifiers, and datasets. Using less weakly-labeled data improves the accuracy of weak supervision pipelines by up to 19% (absolute) on benchmark tasks.
Classification Protocols with Minimal Disclosure CSLAW 2022.
(With Jinshuo Dong and Jason Hartline). [ArXiv| Abstract]

We consider multi-party protocols for classification that are motivated by applications such as e-discovery in court proceedings. We identify a protocol that guarantees that the requesting party receives all responsive documents and the sending party discloses the minimal amount of non-responsive documents necessary to prove that all responsive documents have been received. This protocol can be embedded in a machine learning framework that enables automated labeling of points and the resulting multi-party protocol is equivalent to the standard one-party classification problem (if the one-party classification problem satisfies a natural independence-of-irrelevant-alternatives property). Our formal guarantees focus on the case where there is a linear classifier that correctly partitions the documents.
Effective and Inconspicuous Over-the-Air Adversarial Examples with Adaptive Filtering. ICASSP 2022.
(With Patrick O'Reilly (first author), Pranjal Awasthi and Bryan Pardo). [PDF]
Learning Mixtures of Linear Classifiers. ALT 2022.
(With Aidao Chen and Anindya De). [PMLR/PDF]
Understanding Simultaneous Train and Test Robustness. ALT 2022.
(With Pranjal Awasthi and Sivaraman Balakrishnan). [JMLR/PDF]
Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations. NeurIPS 2021
(With Pranjal Awasthi and Alex Tang). [ArXiv| Abstract]

We present polynomial time and sample efficient algorithms for learning an unknown depth-2 feedforward neural network with general ReLU activations, under mild non-degeneracy assumptions. In particular, we consider learning an unknown network of the form $f(x)=a^\top \sigma(W^\top x+b)$, where x is drawn from the Gaussian distribution, and $\sigma$ is the ReLU activation. Prior works for learning networks with ReLU activations assume that the bias b is zero. In order to deal with the presence of the bias terms, our proposed algorithm consists of robustly decomposing multiple higher order tensors arising from the Hermite expansion of the function f(x). Using these ideas we also establish identifiability of the network parameters under minimal assumptions.
Graph cuts always find a global optimum for Potts models (with a catch) ICML 2021.
(With Hunter Lang and David Sontag). [ArXiv| Abstract]

We prove that the $\alpha$-expansion algorithm for MAP inference always returns a globally optimal assignment for Markov Random Fields with Potts pairwise potentials, with a catch: the returned assignment is only guaranteed to be optimal for an instance within a small perturbation of the original problem instance. In other words, all local minima with respect to expansion moves are global minima to slightly perturbed versions of the problem. On "real-world" instances, MAP assignments of small perturbations of the problem should be very similar to the MAP assignment(s) of the original problem instance. We design an algorithm that can certify whether this is the case in practice. On several MAP inference problem instances from computer vision, this algorithm certifies that MAP solutions to all of these perturbations are very close to solutions of the original instance. These results taken together give a cohesive explanation for the good performance of "graph cuts" algorithms in practice. Every local expansion minimum is a global minimum in a small perturbation of the problem, and all of these global minima are close to the original solution.
Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances AISTATS 2021. (With Hunter Lang, Aravind Reddy and David Sontag). [ArXiv| Abstract]

Several works have shown that perturbation stable instances of the MAP inference problem in Potts models can be solved exactly using a natural linear programming (LP) relaxation. However, most of these works give few (or no) guarantees for the LP solutions on instances that do not satisfy the relatively strict perturbation stability definitions. In this work, we go beyond these stability results by showing that the LP approximately recovers the MAP solution of a stable instance even after the instance is corrupted by noise. This "noisy stable" model realistically fits with practical MAP inference problems: we design an algorithm for finding "close" stable instances, and show that several real-world instances from computer vision have nearby instances that are perturbation stable. These results suggest a new theoretical explanation for the excellent performance of this LP relaxation in practice.
Adversarial robustness via robust low rank representations. NeurIPS 2020.
(With Pranjal Awasthi, Himanshu Jain and Ankit Singh Rawat). [ArXiv| Abstract]

Adversarial robustness measures the susceptibility of a classifier to imperceptible perturbations made to the inputs at test time. In this work we highlight the benefits of natural low rank representations that often exist for real data such as images, for training neural networks with certified robustness guarantees.
Our first contribution is for certified robustness to perturbations measured in $\ell_2$ norm. We exploit low rank data representations to provide improved guarantees over state-of-the-art randomized smoothing-based approaches on standard benchmark datasets such as CIFAR-10 and CIFAR-100.
Our second contribution is for the more challenging setting of certified robustness to perturbations measured in ℓ∞ norm. We demonstrate empirically that natural low rank representations have inherent robustness properties, that can be leveraged to provide significantly better guarantees for certified robustness to ℓ∞ perturbations in those representations. Our certificate of ℓ∞ robustness relies on a natural quantity involving the ∞→2 matrix operator norm associated with the representation, to translate robustness guarantees from $\ell_2$ to $\ell_\infty$ perturbations.
A key technical ingredient for our certification guarantees is a fast algorithm with provable guarantees based on the multiplicative weights update method to provide upper bounds on the above matrix norm. Our algorithmic guarantees improve upon the state of the art for this problem, and may be of independent interest.
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. FOCS 2020.
(With Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa and Zoya Svitkina). [ArXiv| Abstract]

We consider the problem of scheduling $n$ precedence-constrained jobs on $m$ uniformly-related machines in the presence of an arbitrary, fixed communication delay $\rho$. We consider a model that allows job duplication, i.e. processing of the same job on multiple machines, which, as we show, can reduce the length of a schedule (i.e., its makespan) by a logarithmic factor. Our main result is an $O(\log m \log \rho/\log\log \rho)$-approximation algorithm for minimizing makespan, assuming the minimum makespan is at least $\rho$. Our algorithm is based on rounding a linear programming relaxation for the problem, which includes carefully designed constraints capturing the interaction among communication delay, precedence requirements, varying speeds, and job duplication. Our result builds on two previous lines of work, one with communication delay but identical machines (Lepere, Rapine 2002) and the other with uniformly-related machines but no communication delay (Chudak, Shmoys 1999).
We next show that the integrality gap of our mathematical program is $\Omega(\sqrt{\log \rho})$. Our gap construction employs expander graphs and exploits a property of robust expansion and its generalization to paths of longer length. Finally, we quantify the advantage of duplication in scheduling with communication delay. We show that the best schedule without duplication can have makespan $\Omega(\rho/\log\rho)$ or $\Omega(\log m/\log\log m)$ or $\Omega(\log n/\log\log n)$ times that of an optimal schedule allowing duplication. Nevertheless, we present a polynomial time algorithm to transform any schedule to a schedule without duplication at the cost of a $O(\log^2 n\log m)$ factor increase in makespan. Together with our makespan approximation algorithm for schedules allowing duplication, this also yields a polylogarithmic-approximation algorithm for the setting where duplication is not allowed.
Estimating Principal Components under Adversarial Perturbations. COLT 2020.
(With Pranjal Awasthi and Xue Chen). [ArXiv| Abstract]

Robustness is a key requirement for widespread deployment of machine learning algorithms, and has received much attention in both statistics and computer science. We study a natural model of robustness for high-dimensional statistical estimation problems that we call the adversarial perturbation model. An adversary can perturb every sample arbitrarily up to a specified magnitude δ measured in some $\ell_q$ norm, say $\ell_\infty$. Our model is motivated by emerging paradigms such as low precision machine learning and adversarial training.
We study the classical problem of estimating the top-r principal subspace of the Gaussian covariance matrix in high dimensions, under the adversarial perturbation model. We design a computationally efficient algorithm that given corrupted data, recovers an estimate of the top-$r$ principal subspace with error that depends on a robustness parameter that we identify. This parameter corresponds to the $q \to 2$ operator norm of the projector onto the principal subspace, and generalizes well-studied analytic notions of sparsity. Additionally, in the absence of corruptions, our algorithmic guarantees recover existing bounds for problems such as sparse PCA and its higher rank analogs. We also prove that the above dependence on the robustness parameter is almost optimal asymptotically, not just in a minimax sense, but remarkably for every instance of the problem. This instance-optimal guarantee shows that the $q \to 2$ operator norm of the subspace essentially characterizes the estimation error under adversarial perturbations.
Adversarially Robust Low Dimensional Representations. COLT 2021.
(With Pranjal Awasthi, Vaggos Chatziafratis and Xue Chen). [ArXiv| Abstract]

Adversarial or test time robustness measures the susceptibility of a machine learning system to small perturbations made to the input at test time. This has attracted much interest on the empirical side, since many existing ML systems perform poorly under imperceptible adversarial perturbations to the test inputs. On the other hand, our theoretical understanding of this phenomenon is limited, and has mostly focused on supervised learning tasks.
In this work we study the problem of computing adversarially robust representations of data. We formulate a natural extension of Principal Component Analysis (PCA) where the goal is to find a low dimensional subspace to represent the given data with minimum projection error, and that is in addition robust to small perturbations measured in $\ell_q$ norm (say $q=\infty$). Unlike PCA which is solvable in polynomial time, our formulation is computationally intractable to optimize as it captures the well-studied sparse PCA objective.
We show the following algorithmic and statistical results. - Polynomial time algorithms in the worst-case that achieve constant factor approximations to the objective while only violating the robustness constraint by a constant factor. - We prove that our formulation (and algorithms) also enjoy significant statistical benefits in terms of sample complexity over standard PCA on account of a ``regularization effect'', that is formalized using the well-studied spiked covariance model. - Surprisingly, we show that our algorithmic techniques can also be made robust to corruptions in the training data, in addition to yielding representations that are robust at test time! Here an adversary is allowed to corrupt potentially every data point up to a specified amount in the $\ell_q$ norm. We further apply these techniques for mean estimation and clustering under adversarial corruptions to the training data.
On Robustness to Adversarial Examples and Polynomial Optimization. NeurIPS 2019.
(With Pranjal Awasthi and Abhratanu Dutta). [Arxiv|Slides | Abstract]

We study the design of computationally efficient algorithms with provable guarantees, that are robust to adversarial (test time) perturbations. While there has been an explosion of recent work on this topic due to its connections to test time robustness of deep networks, there is limited theoretical understanding of several basic questions including \emph{when and how can one design provably robust learning algorithms?}, and \emph{what is the price of achieving robustness to adversarial examples in a computationally efficient manner?}
The main contribution of this work is to exhibit a strong connection between achieving robustness to adversarial examples, and a rich class of polynomial optimization problems, thereby making progress on the above questions. In particular, we leverage this connection to (a) design the first computationally efficient robust algorithms with provable guarantees for a large class of hypothesis, namely linear classifiers and degree-$2$ polynomial threshold functions~(PTFs), (b) give a precise characterization of the price of achieving robustness in a computationally efficient manner for these classes, (c) design efficient algorithms to certify robustness and generate adversarial attacks in a principled manner for $2$-layer neural networks. We empirically demonstrate the effectiveness of these attacks on real data.
Smoothed Analysis in Unsupervised Learning via Decoupling FOCS 2019.
(With Aditya Bhaskara, Aidao Chen and Aidan Perreault). [ArXiv| Abstract]

Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in unsupervised learning and high-dimensional data analysis. While polynomial time smoothed analysis guarantees have been obtained for worst-case intractable problems like tensor decompositions and learning mixtures of Gaussians, such guarantees have been hard to obtain for several other important problems in unsupervised learning. A core technical challenge is obtaining lower bounds on the least singular value for random matrix ensembles with dependent entries, that are given by low-degree polynomials of a few base underlying random variables.
In this work, we address this challenge by obtaining high-confidence lower bounds on the least singular value of new classes of structured random matrix ensembles of the above kind. We then use these bounds to obtain polynomial time smoothed analysis guarantees for the following three important problems in unsupervised learning:
1. Robust subspace recovery, when the fraction $\alpha$ of inliers in the d-dimensional subspace $T \subset \mathbb{R}^n$ is at least $\alpha >(d/n)^{\ell}$ for any constant integer $\ell>0$. This contrasts with the known worst-case intractability when $\alpha< d/n$, and the previous smoothed analysis result which needed $\alpha > d/n$ (Hardt and Moitra, 2013).
2. Higher order tensor decompositions, where we generalize the so-called FOOBI algorithm of Cardoso to find order-$\ell$ rank-one tensors in a subspace. This allows us to obtain polynomially robust decomposition algorithms for $2\ell$'th order tensors with rank $O(n^{\ell})$.
3. Learning overcomplete hidden markov models, where the size of the state space is any polynomial in the dimension of the observations. This gives the first polynomial time guarantees for learning overcomplete HMMs in a smoothed analysis model.
Block Stability for MAP inference AISTATS 2019.
(With Hunter Lang and David Sontag). [ArXiv| Abstract]

To understand the empirical success of approximate MAP inference, recent work (Lang et al., 2018) has shown that some popular approximation algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise potentials are (adversarially) perturbed. Unfortunately, this strong condition does not seem to be satisfied in practice. In this paper, we introduce a significantly more relaxed condition that only requires blocks (portions) of an input instance to be stable. Under this block stability condition, we prove that the pairwise LP relaxation is persistent on the stable blocks. We complement our theoretical results with an empirical evaluation of real-world MAP inference instances from computer vision. We design an algorithm to find stable blocks, and find that these real instances have large stable regions. Our work gives a theoretical explanation for the widespread empirical phenomenon of persistency for this LP relaxation.
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports FOCS 2018.
(With Pranjal Awasthi). [ArXiv| Abstract]

Dictionary learning is a popular approach for inferring a hidden basis or dictionary in which data has a sparse representation. Data generated from the dictionary A (an n by m matrix, with m > n in the over-complete setting) is given by $Y = AX$ where X is a matrix whose columns have supports chosen from a distribution over k-sparse vectors, and the non-zero values chosen from a symmetric distribution. Given Y, the goal is to recover A and X in polynomial time. Existing algorithms give polytime guarantees for recovering incoherent dictionaries, under strong distributional assumptions both on the supports of the columns of X, and on the values of the non-zero entries. In this work, we study the following question: Can we design efficient algorithms for recovering dictionaries when the supports of the columns of X are arbitrary? To address this question while circumventing the issue of non-identifiability, we study a natural semirandom model for dictionary learning where there are a large number of samples y=Ax with arbitrary k-sparse supports for x, along with a few samples where the sparse supports are chosen uniformly at random. While the few samples with random supports ensures identifiability, the support distribution can look almost arbitrary in aggregate. Hence existing algorithmic techniques seem to break down as they make strong assumptions on the supports. Our main contribution is a new polynomial time algorithm for learning incoherent over-complete dictionaries that works under the semirandom model. Additionally the same algorithm provides polynomial time guarantees in new parameter regimes when the supports are fully random. Finally using these techniques, we also identify a minimal set of conditions on the supports under which the dictionary can be (information theoretically) recovered from polynomial samples for almost linear sparsity, i.e., $k=\widetilde{O}(n)$.
Clustering Semi-Random Mixtures of Gaussians ICML 2018.
(With Pranjal Awasthi). [ArXiv| Abstract]

Gaussian mixture models (GMM) are the most widely used statistical model for the k-means clustering problem and form a popular framework for clustering in machine learning and data analysis. In this paper, we propose a natural semi-random model for k-means clustering that generalizes the Gaussian mixture model, and that we believe will be useful in identifying robust algorithms. In our model, a semi-random adversary is allowed to make arbitrary "monotone" or helpful changes to the data generated from the Gaussian mixture model. Our first contribution is a polynomial time algorithm that provably recovers the ground-truth up to small classification error w.h.p., assuming certain separation between the components. Perhaps surprisingly, the algorithm we analyze is the popular Lloyd's algorithm for k-means clustering that is the method-of-choice in practice. Our second result complements the upper bound by giving a nearly matching information-theoretic lower bound on the number of misclassified points incurred by any k-means clustering algorithm on the semi-random model.
Optimality of Approximate Inference Algorithms on Stable Instances AISTATS 2018.
(With Hunter Lang and David Sontag). [ArXiv| Abstract]

Approximate algorithms for structured prediction problems---such as the popular alpha-expansion algorithm (Boykov et al. 2001) in computer vision---typically far exceed their theoretical performance guarantees on real-world instances. These algorithms often find solutions that are very close to optimal. The goal of this paper is to partially explain the performance of alpha-expansion on MAP inference in Ferromagnetic Potts models (FPMs). Our main results use the connection between energy minimization in FPMs and the Uniform Metric Labeling problem to give a stability condition under which the alpha-expansion algorithm provably recovers the optimal MAP solution. This theoretical result complements the numerous empirical observations of alpha-expansion's performance. Additionally, we give a different stability condition under which an LP-based algorithm recovers the optimal solution.
On Learning Mixtures of Well-Separated Gaussians FOCS 2017.
(With Oded Regev). [ArXiv|PDF | Abstract]

We consider the problem of efficiently learning mixtures of a large number of spherical Gaussians, when the components of the mixture are well separated. In the most basic form of this problem, we are given samples from a uniform mixture of $k$ standard spherical Gaussians with means \mu_1,\ldots,\mu_k in R^d, and the goal is to estimate the means up to accuracy $\delta$ using $poly(k,d, 1/\delta)$ samples. In this work, we study the following question: what is the minimum separation needed between the means for solving this task? The best known algorithm due to Vempala and Wang [JCSS 2004] requires a separation of roughly $\min\{k,d\}^{1/4}$. On the other hand, Moitra and Valiant [FOCS 2010] showed that with separation $o(1)$, exponentially many samples are required. We address the significant gap between these two bounds, by showing the following results.
1. We show that with separation $o(\sqrt{\log k})$, super-polynomially many samples are required. In fact, this holds even when the $k$ means of the Gaussians are picked at random in $d=O(\log k)$ dimensions.
2. We show that with separation $\Omega(\sqrt{\log k})$, $\poly(k,d,1/\delta)$ samples suffice. Notice that the bound on the separation is independent of $\delta$. This result is based on a new and efficient ``accuracy boosting'' algorithm that takes as input coarse estimates of the true means and in time (and samples) $\poly(k,d, 1/\delta)$ outputs estimates of the means up to arbitrarily good accuracy $\delta$ assuming the separation between the means is $\Omega(\min\{\sqrt{\log k},\sqrt{d}\})$ (independently of $\delta$). The idea of the algorithm is to iteratively solve a ``diagonally dominant'' system of non-linear equations.

We also (1) present a computationally efficient algorithm in $d=O(1)$ dimensions with only $\Omega(\sqrt{d})$ separation, and (2) extend our results to the case that components might have different weights and variances. These results together essentially characterize the optimal order of separation between components that is needed to learn a mixture of $k$ spherical Gaussians with polynomial samples.
Clustering Stable Instances of Euclidean k-means NIPS 2017.
(With Abhratanu Dutta and Alex Wang). [ArXiv| Abstract]

The Euclidean k-means problem is arguably the most widely-studied clustering problem in machine learning. While the k-means objective is NP-hard in the worst-case, practitioners have enjoyed remarkable success in applying heuristics like Lloyd's algorithm for this problem. To address this disconnect, we study the following question: what properties of real-world instances will enable us to design efficient algorithms and prove guarantees for finding the optimal clustering? We consider a natural notion called additive perturbation stability that we believe captures many practical instances. Stable instances have unique optimal k-means solutions that do not change even when each point is perturbed a little (in Euclidean distance). This captures the property that the k-means optimal solution should be tolerant to measurement errors and uncertainty in the points. We design efficient algorithms that provably recover the optimal clustering for instances that are additive perturbation stable. When the instance has some additional separation, we show an efficient algorithm with provable guarantees that is also robust to outliers. We complement these results by studying the amount of stability in real datasets and demonstrating that our algorithm performs well on these benchmark datasets.
Approximation Algorithms for Label Cover and the Log-Density Threshold SODA 2017.
(With Eden Chlamtac, Pasin Manurangsi and Dana Moshkovitz). [ArXiv|SODA | Abstract]

Many known optimal NP-hardness of approximation results are reductions from a problem called \textsc{Label-Cover}. The input is a bipartite graph $G=(L,R,E)$ and each edge $e=(x,y)\in E$ carries a projection $\pi_e$ that maps labels to $x$ to labels to $y$. The objective is to find a labeling of the vertices that satisfies as many of the projections as possible. It is believed that the best approximation ratio efficiently achievable for Label-Cover is of the form $N^{-c}$ where $N=nk$, $n$ is the number of vertices, $k$ is the number of labels, and $c \in (0,1)$ is some constant.
Inspired by a framework originally developed for Densest $k$-Subgraph, we propose a ``log density threshold'' for the approximability of Label-Cover. Specifically, we suggest the possibility that the Label-Cover approximation problem undergoes a computational phase transition at the same threshold at which local algorithms for its random counterpart fail. This threshold is $N^{3-2\sqrt{2}}\approx N^{-0.17}$. We then design, for any $\varepsilon>0$, a polynomial-time approximation algorithm for {\em semi-random} \textsc{Label-Cover} whose approximation ratio is $N^{3-2\sqrt{2}+\varepsilon}$. In our semi-random model, the input graph is random (or even just expanding), and the projections on the edges are arbitrary.
For worst-case Label-Cover we show a polynomial-time algorithm whose approximation ratio is roughly $N^{-0.233}$. The previous best efficient approximation ratio was $N^{-0.25}$. We present some evidence towards an $N^{-c}$ threshold by constructing integrality gaps for $N^{\Omega(1)}$ rounds of the Sum-of-squares/Lasserre hierarchy of the natural relaxation of Label Cover. For general 2CSP the ``log density threshold'' is $N^{-0.25}$, and we give a polynomial-time algorithm in the semi-random model whose approximation ratio is $N^{-0.25+\varepsilon}$ for any $\varepsilon>0$.
Learning Communities in the Presence of Errors COLT 2016.
(With Konstantin Makarychev and Yury Makarychev). [ ArXiv | Abstract]

We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige---Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) posed an open question about whether an almost exact recovery is possible when the adversary is allowed to add o(n) edges. Our work answers this question affirmatively even in the case of k>2 communities.

We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is \epsilon m close to SBM in the Kullback---Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree APPROX 2015.
(With Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, David Witmer and John Wright). [ ArXiv | Abstract]

We show that for any odd k and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2+ c/\sqrt{D} fraction of constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2+ D^{−3/4} fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a \mu +c/\sqrt{D} fraction of constraints, where \mu is the fraction that would be satisfied by a uniformly random assignment.
Correlation Clustering with Noisy, Partial Information COLT 2015.
(With Konstantin Makarychev and Yury Makarychev). [ ArXiv | Abstract]

In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value (1+\delta)opt-cost+O_\delta(n log^3 n) with high probability, where opt-cost is the value of the optimal solution (for every \delta>0). The second algorithm finds the ground truth clustering with an arbitrarily small classification error (under some additional assumptions on the instance).
Learning Mixtures of Ranking Models. NIPS 2014 .
(With Pranjal Awasthi, Avrim Blum and Or Sheffet). [ ArXiv |Abstract]

This work concerns learning probabilistic models for ranking data in a heterogeneous population. The specific problem we study is learning the parameters of a Mallows Mixture Model . Despite being widely studied, current heuristics for this problem do not have theoretical guarantees and can get stuck in bad local optima.

We present the first polynomial time algorithm which provable learns the parameters of a mixture of two Mallows models. A key component of our algorithm is a novel use of tensor decomposition techniques to learn the top-k prefix in both the rankings. In particular, our results imply that in order to recover the top k-rankings from a heterogeneous population, it is enough for each user to just specify their top-3 (unordered) preferences.
Constant Factor Approximations for Balanced Cut in the random PIE model STOC 2014.
(With Konstantin Makarychev and Yury Makarychev). [ ArXiv | Abstract]

We propose and study a new average-case model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than previously studied average-case models like semi-random models, random planted partitioning models and stochastic block models, and can capture real-world network models like preferential attachment models. We give constant factor approximations for Balanced Cut in this model.

The model : Consider a set of vertices V partitioned into two clusters L and R of equal size. Let G be an arbitrary graph on V with no edges between L and R. Let E_random be a set of edges sampled from an arbitrary permutation-invariant distribution (a distribution that is invariant under renaming of vertices in L and in R). Then we say that G + E_random is a graph with permutation-invariant random edges. For example, in a social network formed by the superposition of separate networks representing different types of ties (say geographic and professional), these different networks are independent.

We present an approximation algorithm for the Balanced Cut problem that finds a balanced cut of cost O(E_random) + n.polylog(n) in this model. In the most interesting regime, this is a constant factor approximation with respect to the cost of the planted cut.
Smoothed Analysis of Tensor Decompositions. STOC 2014.
(With Aditya Bhaskara, Moses Charikar and Ankur Moitra) [ PDF | ArXiv | Abstract ]

Low rank tensor decompositions are a powerful tool for learning generative models, and uniqueness results give them a significant advantage over matrix decomposition methods. However, tensors pose significant algorithmic challenges and tensors analogs of much of the matrix algebra toolkit are unlikely to exist because of hardness results. Efficient decomposition in the overcomplete case (where rank exceeds dimension) is particularly challenging. We introduce a smoothed analysis model for studying these questions and develop an efficient algorithm for tensor decomposition in the highly overcomplete case (rank polynomial in the dimension). In this setting, we show that our algorithm is robust to inverse polynomial error -- a crucial property for applications in learning since we are only allowed a polynomial number of samples. While algorithms are known for exact tensor decomposition in some overcomplete settings, these are not known to be stable to noise.

Our main technical contribution is to show that tensor products of perturbed vectors are linearly independent in a robust sense (i.e. the associated matrix has singular values that are at least an inverse polynomial). This key result paves the way for applying tensor methods to learning problems in the smoothed setting. In particular, we use it to obtain results for learning multi-view models and mixtures of axis-aligned Gaussians where there are many more "components" than dimensions. The assumption here is that the model is not adversarially chosen, formalized by a perturbation of model parameters. We believe this an appealing way to analyze realistic instances of learning problems, since this framework allows us to overcome many of the usual limitations of using tensor methods.
Uniqueness of Tensor Decompositions and Polynomial Identifiability of Latent Variable Models.
COLT 2014. (With Aditya Bhaskara and Moses Charikar) [PDF | ArXiv | Abstract ]

We give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: we prove that given a tensor whose decomposition satisfies a robust form of Kruskal's rank condition, it is possible to approximately recover the decomposition if the tensor is known up to a sufficiently small (inverse polynomial) error.

Kruskal's theorem has found many applications in proving the identifiability of parameters for variouslatent variable models and mixture models such as Hidden Markov models, topic models etc. Our robust version immediately implies identifiability using only polynomially many samples in many of these settings. This polynomial identifiability is an essential first step towards efficient learning algorithms for these models.

Recently, algorithms based on tensor decompositions have been used to estimate the parameters of various hidden variable models efficiently in special cases as long as they satisfy certain "non-degeneracy" properties. Our methods give a way to go beyond this non-degeneracy barrier, and establish polynomial identifiability of the parameters under much milder conditions. Given the importance of Kruskal's theorem in the tensor literature, we expect that this robust version will have several applications beyond the settings we explore in this work.
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. SODA 2014.
(With Konstantin Makarychev and Yury Makarychev) [PDF | ArXiv | Abstract]

We investigate the notion of stability proposed by Bilu and Linial. We obtain an exact polynomial-time algorithm for $\gamma$-stable Max Cut instances with $\gamma >= c\sqrt{log n}loglog n$ for some absolute constant $c > 0$. Our algorithm is robust: it never returns an incorrect answer; if the instance is $\gamma$-stable, it finds the maximum cut, otherwise, it either finds the maximum cut or certifies that the instance is not $\gamma$-stable. We prove that there is no robust polynomial-time algorithm for $\gamma$-stable instances of Max Cut when $\gamma < \alpha_{SC}(n/2)$, where $\alpha_{SC}$ is the best approximation factor for Sparsest Cut with non-uniform demands.

Our algorithm is based on semidefinite programming. We show that the standard SDP relaxation for Max Cut (with $\ell_2^2$ triangle inequalities) is integral if $\gamma \geq D_{\ell_2^2\to \ell_1}(n)$, where $D_{\ell_2^2\to \ell_1}(n)$ is the least distortion with which every n point metric space of negative type embeds into $\ell_1$. On the negative side, we show that the SDP relaxation is not integral when $\gamma < D_{\ell_2^2\to \ell_1}(n/2)$. Moreover, there is no tractable convex relaxation for $\gamma$-stable instances of Max Cut when $\gamma < \alpha_{SC}(n/2)$. That suggests that solving $\gamma$-stable instances with $\gamma =o(\sqrt{\log n})$ might be difficult or impossible.

Our results significantly improve previously known results. The best previously known algorithm for $\gamma$-stable instances of Max Cut required that $\gamma \geq c\sqrt{n}$ (for some $c > 0$) [Bilu, Daniely, Linial, and Saks]. No hardness results were known for the problem. Additionally, we present an algorithm for 4-stable instances of Minimum Multiway Cut. We also study a relaxed notion of weak stability.
Sorting noisy data with partial information. ITCS 2013.
(With Konstantin Makarychev and Yury Makarychev) [PDF | Abstract]
nd the minimum set of edges (arcs) whose removal makes a given graph a directed acyclic graph (DAG). The interest in FAS stems from its numerous applications in sorting and ranking based on pairwise information, removing cyclic dependencies etc. However, the best known algorithm for this problem only gives a polylogarithmic approximation in the worst-case, and constant factor approximations have been elusive.
Since real-world instances are unlikely to behave like worst-case instances, a compelling question is : can we design better algorithms for realistic average case instances? We propose two realistic average-case models for the problem, and present new approximation algorithms which obtain a PTAS and constant factor approximations in these two models.
Approximation algorithms for Semi-random Graph Partitioning problems. STOC 2012.
(With Konstantin Makarychev and Yury Makarychev) [PDF | ArXiv | Abstract]

We propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real
WThe model is more flexible than the semi-random model of Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and Sipser.

In our semi-random graph partitioning model, we need just edges across different clusters to be (semi)-random. The edges inside clusters can be completely arbitrary (unlike previous models).

We develop a general framework for solving semi-random instances using new SDP-based techniques and apply it to several problems of interest. We present constant factor approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut and Small-Set Expansion problems. We also show how to almost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithms work in a wider range of parameters than algorithms for previously studied random and semi-random models.
Polynomial Integrality gaps for Strong relaxations of Densest k-subgraph. SODA 2012.
(With Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami and Yuan Zhou) [PDF | ArXiv | Abstract]

The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significant gap between known upper and lower bounds for DkS: the current best algorithm gives an ~ $O(n^{1/4})$ approximation, while even showing a small constant factor hardness requires significantly stronger assumptions than P != NP. In addition to interest in designing better algorithms, a number of recent results have exploited the conjectured hardness of densest k-subgraph and its variants. Thus, understanding the approximability of DkS is an important challenge. In this work, we give evidence for the hardness of approximating DkS within polynomial factors. Specifically, we expose the limitations of strong semidefinite programs from SDP hierarchies in solving densest k-subgraph. Our results include:

* A lower bound of $\Omega(n^{1/4}/\log^3 n)$ on the integrality gap for $\Omega(\log n/\log \log n)$ rounds of the Sherali-Adams relaxation for DkS. This also holds for the relaxation obtained from Sherali-Adams with an added SDP constraint. Our gap instances are in fact Erdos-Renyi random graphs.
* For every $\epsilon > 0$, a lower bound of $n^{2/53-\epsilon}$ on the integrality gap of $n^{\Omega(\epsilon)}$ rounds of the Lasserre SDP relaxation for DkS, and an $n^{Omega_\epsilon(1)}$ gap for $n^{1-\epsilon}$ rounds. Our construction proceeds via a reduction from random instances of a certain Max-CSP over large domains. In the absence of inapproximability results for DkS, our results show that even the most powerful SDPs are unable to beat a factor of $n^{\Omega(1)}$, and in fact even improving the best known $n^{1/4}$ factor is a barrier for current techniques.
Algorithms and Hardness of the k-route cuts problem. SODA 2012.
(With Julia Chuzhoy, Yury Makarychev and Yuan Zhou) [PDF | ArXiv | Abstract]

We study the k-route cut problem: given an undirected edge-weighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of source-sink pairs, and an integer connectivity requirement k, the goal is to find a minimum-weight subset E' of edges to remove, such that the connectivity of every pair (s_i, t_i) falls below k. Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most (k-1) edge-disjoint paths connecting s_i to t_i in G \ E', while in the vertex-connectivity version, NC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithms have been known for the special case where k >= 3, but no non-trivial approximation algorithms were known for any value k>3, except in the single-source setting. We show an O(k log^{3/2}r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and NC-kRC, where the connectivity requirement k is violated by a constant factor. We complement these upper bounds by proving that NC-kRC is hard to approximate to within a factor of k^{eps} for some fixed eps>0.

We then turn to study a simpler version of NC-kRC, where only one source-sink pair is present. We give a simple bi-criteria approximation algorithm for this case, and show evidence that even this restricted version of the problem may be hard to approximate. For example, we prove that the single source-sink pair version of NC-kRC has no constant-factor approximation, assuming Feige's Random k-AND assumption.
On Quadratic Programming with a ratio objective. ICALP 2012.
(With Aditya Bhaskara, Moses Charikar and Rajsekar Manokaran) [PDF | ArXiv ]
Approximating the matrix p-norm. SODA 2011.
(With Aditya Bhaskara) [PDF | Abstract]

We consider the problem of computing the q->p norm of a matrix A, which is defined for p,q >= 1, as |A|_q->p = Max_x ||Ax||_p, where ||x||_q=1
This is in general a non-convex optimization problem, and is a natural generalization of the well-studied question of computing singular values ( when p=q=2). Different settings of parameters give rise to a variety of known interesting problems (such as the Grothendieck problem when p=1 and q=\infty ). Our first result is an efficient algorithm for computing the q->p norm of matrices with non-negative entries, when q >= p >= 1. The algorithm we analyze can be seen as an analog of power iteration for computing eigenvalues.
We then present an application of our techniques in the oblivious routing setting: we make constructive a recent existential result of Englert and Racke on O(log n) competitive oblivious routing schemes in the l_p norm.
On the other hand, for general matrices, we show "almost polynomial" factor hardness for 2 < p <= q and p <= q < 2 if NP does not have quasi-polynomial time algorithms.
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph. STOC 2010.
(With Aditya Bhaskara, Moses Charikar, Eden Chlamtac and Uri Feige) [PDF | Abstract]

In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg~\cite{FKP}, gives an approximation ratio of $n^{1/3 - \epsilon}$ for some specific $\epsilon > 0$ (estimated by those authors at around $\epsilon = 1/60$).

We present an algorithm that for every $\epsilon> 0$ approximates the Densest $k$-Subgraph problem within a ratio of $n^{1/4 + \epsilon}$ in time $n^{O(1/\epsilon)}$. If allowed to run for time $n^{O(\log n)}$, our algorithm achieves an approximation ratio of $O(n^{1/4})$. Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from random graphs with planted dense subgraphs -- the approximation ratio we achieve for the general case matches the ``distinguishing ratio'' we obtain for this planted problem. Achieving a distinguishing ratio of $o(n^{1/4})$ for the planted problem (in polynomial time) is beyond the reach of our current techniques.

At a high level, our algorithms involve cleverly counting appropriately defined trees of constant size in $G$, and using these counts to identify the vertices of the dense subgraph. Our algorithm is based on the following principle. We say that a graph $G(V,E)$ has log-density $\alpha$ if its average degree is $\Theta(|V|^{\alpha})$. The algorithmic core of our result is a family of algorithms that output $k$-subgraphs of nontrivial density whenever the log-density of the densest $k$-subgraph is larger than the log-density of the host graph.

Finally, we extend this algorithm to obtain an $O(n^{1/4 - \epsilon})$-approximation algorithm which runs in time $O(2^{n^{O(\epsilon)}})$ and also explore various approaches to obtain better approximation algorithms in restricted parameter settings for random instances.