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. I am particularly interested in Approximation Algorithms for NP-hard optimization problems from both Worst-Case and Average-Case perspectives.

• 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.

• 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.

• 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 |

• 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.



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

Some useful links for people in the theoretical computer science community maybe:

• Videos of CS theory talks at Princeton