Aravindan Vijayaraghavan

I am currently a Simons Foundation Postdoctoral Research Fellow with the Theory Group at Carnegie Mellon University .

I obtained my PhD from Princeton University in the Department of Computer Science. My advisor was Prof. Moses Charikar.

Prior to that, I finished my bachelor's degree in Computer Science and Engineering 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.

My outdated CV can be found here.

My research interests are broadly in the field of Theoretical Computer Science, in designing efficient algorithms with provable guarantees for problems in Combinatorial Optimization and Machine Learning. I am particularly interested in algorithms for approximating NP-hard optimization problems and learning probabilistic models, from both Worst-Case and Average-Case perspectives.

• Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability of Latent Variable Models
With Aditya Bhaskara and Moses Charikar.
ArXiv Preprint. | 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 various latent 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
With Konstantin Makarychev and Yury Makarychev
SODA 2014. Symposium on Discrete Algorithms 2014. | 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
With Konstantin Makarychev and Yury Makarychev
ITCS 2013. Innovations in Theoretical Computer Science 2013. | PDF | Abstract

We consider minimum Feedback Arc Set (FAS), a basic optimization problem on directed graphs. The problem asks to find 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
With Konstantin Makarychev and Yury Makarychev
STOC 2012. Symposium on the Theory of Computing 2012. | 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–world instances. The 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
With Aditya Bhaskara,Moses Charikar, Venkatesan Guruswami and Yuan Zhou
SODA 2012. Symposium on Discrete Algorithms 2012. | 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
With Julia Chuzhoy,Yury Makarychev and Yuan Zhou
SODA 2012. Symposium on Discrete Algorithms 2012. | 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
With Aditya Bhaskara,Moses Charikar and Rajsekar Manokaran
ICALP 2012. Intl. Colloquium on Automata, Lang. and Prog. | PDF | ArXiv |

• Approximating the matrix p-norm
With Aditya Bhaskara.
SODA 2011. Symposium on Discrete Algorithms 2011. | 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
With Aditya Bhaskara, Moses Charikar, Eden Chlamtac and Uri Feige.
STOC 2010. Symposium on the Theory of Computing 2010. | 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.




Some older work includes
• Non-cooperative Bundling games
With Ravishankar Krishnaswamy, Pandu Rangan Chandrasekaran and Ravi Sundaram . Manuscript. Abstract
Bundling is a basic problem in commerce. We define and study the Bundling Game: each of n players with a unique product to sell can choose to sell their products in bundles with other players' products so as to maximize payoff; the players have knowledge of the valuations of m (potential) buyers for each of the products. We define two natural classes of payoff functions - Fair Profit Sharing Functions (FPSFs) and Incentive Functions (IFs). For FPSFs we prove the surprising impossibility result that there exists no Fair Profit Sharing Payoff Function that can always guarantee stability. We counterbalance this result by showing that pure Nash equilibria always exist for IFs and obtain tight bounds on the Price of Anarchy. In particular, the revenue maximizing bundling is a pure Nash equilibrium. Motivated by the bundling game, we present hardness results and approximation algorithms for finding revenue maximizing bundlings and bundles and associated variants.

I have served as a Teaching Assistant for the following courses at Princeton University

• COS 340 - Reasoning about Computation
• COS 226 - Data Structures and Algorithms

I also helped as a Teaching Assistant for the following introductory computer science course at the Indian Institute of Technology, Madras.

• CS110 - Introduction to Computing