6 citations · 10 across the 3 of their papers we have counts for
3 papers · 1 filter
How to Play Unique Games against a Semi-Random Adversary
Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
In this paper, we study the average case complexity of the Unique Games problem. We propose a natural semi-random model, in which a unique game instance is generated in several ste…
On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data
Howard Karloff, Flip Korn, Konstantin Makarychev +1
This paper studies the "explanation problem" for tree- and linearly-ordered array data, a problem motivated by database applications and recently solved for the one-dimensional tre…
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…