7 citations · 9 across the 3 of their papers we have counts for
3 papers
cs.DS2016★ 1 cited
A Framework for Analyzing Resparsification Algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng +1
A spectral sparsifier of a graph is a sparser graph that approximately preserves the quadratic form of , i.e. for all vectors , , where $…
cs.DS2014★ 1 cited
Simultaneous Approximation of Constraint Satisfaction Problems
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva
Given collections of 2SAT clauses on the same set of variables , can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such…
cs.LG2012★ 7 cited
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
Sanjeev Arora, Rong Ge, Ankur Moitra +1
We present a new algorithm for Independent Component Analysis (ICA) which has provable performance guarantees. In particular, suppose we are given samples of the form …