23 citations · 146 across the 41 of their papers we have counts for
4 papers · 1 filter
Min-Max Graph Partitioning and Small Set Expansion
Nikhil Bansal, Uriel Feige, Robert Krauthgamer +5
We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maxi…
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…
The Grothendieck constant is strictly smaller than Krivine's bound
Mark Braverman, Konstantin Makarychev, Yury Makarychev +1
We prove that , where is the Grothendieck constant.
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…