28 citations · 130 across the 32 of their papers we have counts for
3 papers · 1 filter
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…