23 citations · 146 across the 41 of their papers we have counts for
3 papers · 1 filter
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…
A bi-criteria approximation algorithm for Means
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko +1
We consider the classical -means clustering problem in the setting bi-criteria approximation, in which an algoithm is allowed to output clusters, and must produce a clu…
Satisfiability of Ordering CSPs Above Average
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability…