38 citations · 171 across the 26 of their papers we have counts for
Showing 2014 · cs.CCShow all
2 papers · 2 filters
cs.CC2014★ 6 cited
Lower bounds on the size of semidefinite programming relaxations
James R. Lee, Prasad Raghavendra, David Steurer
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, a…
cs.CC2014★ 38 cited
Computational Limits for Matrix Completion
Moritz Hardt, Raghu Meka, Prasad Raghavendra +1
Matrix Completion is the problem of recovering an unknown real-valued low-rank matrix from a subsample of its entries. Important recent results show that the problem can be solved…