6 citations · 10 across the 3 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.DS2011★ 4 cited
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…
cs.DS2011★ 6 cited
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…