57 citations · 164 across the 38 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
cs.DM2009★ 1 cited
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
Alexandra Kolla, Yury Makarychev, Amin Saberi +1
We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs an…
cs.DS2009
How to Play Unique Games on Expanders
Konstantin Makarychev, Yury Makarychev
In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a -satisfiabl…
cs.DS2009★ 4 cited
Balanced allocation: Memory performance tradeoffs
Itai Benjamini, Yury Makarychev
Suppose we sequentially put balls into bins. If we put each ball into a random bin then the heaviest bin will contain balls with high probability.…