28 citations · 130 across the 32 of their papers we have counts for
18 papers · 1 filter
Higher-Order Cheeger Inequality for Partitioning with Buffers
Konstantin Makarychev, Yury Makarychev, Liren Shan +1
We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph . The buffered expansion of a set with…
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan
We study the problem of finding elements in the intersection of an arbitrary conic variety in with a given linear subspace (where can be the real or com…
Learning a mixture of two subspaces over finite fields
Aidao Chen, Anindya De, Aravindan Vijayaraghavan
We study the problem of learning a mixture of two subspaces over . The goal is to recover the individual subspaces, given samples from a (weighted) mixture of sampl…
Efficient Tensor Decomposition
Aravindan Vijayaraghavan
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 an…
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa +2
We consider the problem of scheduling precedence-constrained jobs on uniformly-related machines in the presence of an arbitrary, fixed communication delay . We consider…
Adversarially Robust Low Dimensional Representations
Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen +1
Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical…
Smoothed Analysis in Unsupervised Learning via Decoupling
Aditya Bhaskara, Aidao Chen, Aidan Perreault +1
Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in unsupervised learning and high-dimensional data analysis. While polynomial time smoothed analysi…
Clustering Semi-Random Mixtures of Gaussians
Pranjal Awasthi, Aravindan Vijayaraghavan
Gaussian mixture models (GMM) are the most widely used statistical model for the -means clustering problem and form a popular framework for clustering in machine learning and da…
On Learning Mixtures of Well-Separated Gaussians
Oded Regev, Aravindan Vijayaraghavan
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…
Learning Communities in the Presence of Errors
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
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…
Constant Factor Approximation for Balanced Cut in the PIE model
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than p…
Correlation Clustering with Noisy Partial Information
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
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 Clusterin…
Smoothed Analysis of Tensor Decompositions
Aditya Bhaskara, Moses Charikar, Ankur Moitra +1
Low rank tensor decompositions are a powerful tool for learning generative models, and uniqueness results give them a significant advantage over matrix decomposition methods. Howev…
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
We investigate the notion of stability proposed by Bilu and Linial. We obtain an exact polynomial-time algorithm for -stable Max Cut instances with $γ\geq c\sqrt{\log n}\log\log…
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
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…
Approximation Algorithms for Semi-random Graph Partitioning Problems
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
In this paper, 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…
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami +2
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 significan…
Approximating Matrix p-norms
Aditya Bhaskara, Aravindan Vijayaraghavan
We consider the problem of computing the q->p norm of a matrix A, which is defined for p,q \ge 1, as |A|_{q->p} = max_{x !=0 } |Ax|_p / |x|_q. This is in general a non-convex optim…