28 citations · 130 across the 32 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.DS2015★ 8 cited
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…
cs.CC2015★ 8 cited
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
We show that for any odd and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…