How to Play Unique Games on Expanders (2009)
Makarychev, Konstantin, Makarychev, Yury
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 $(1-\varepsilon)$-satisfiable instance of...
Balanced Allocation: Memory Performance Tradeoffs (2009)
Benjamini, Itai, Makarychev, Yury
Suppose that we sequentially put $n$ balls into $n$ bins. If we put each ball into a random bin then the heaviest bin will contain $\log n /\log\log n$ balls (w.h.p.). However, Azar, Broder, Karlin...
Amit Agarwal, Konstantin Makarychev, Moses Charikar, Yury Makarychev
We give O ( √ log n)-approximation algorithms for the Min
Amit Agarwal, Konstantin Makarychev, Moses Charikar, Yury Makarychev
We give O ( √ log n)-approximation algorithms for the Min
Eigenvalue multiplicity and volume growth (2008)
Lee, James R., Makarychev, Yury
Let $G$ be a finite group with symmetric generating set $S$, and let $c = \max_{R > 0} |B(2R)|/|B(R)|$ be the doubling constant of the corresponding Cayley graph, where $B(R)$ denotes an $R$-ball in...
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this note we present an approximation algorithm for MAX 2SAT that given a (1 − ε) satisfiable instance finds an assignment of variables satisfying a 1 − O ( √ ε) fraction of all...
On the Advantage over Random for Maximum Acyclic Subgraph (2008)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains 1/2+δ fraction of all edges, our algorithm...
Abstract Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems (2008)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this paper we present approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1 − ε) satisfiable 2CSP our first...
Abstract Directed Metrics and Directed Graph Partitioning Problems (2008)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
The theory of embeddings of finite metrics has provided a powerful toolkit for graph partitioning problems in undirected graphs. The connection comes from the fact that the integrality gaps of...
Dimension Reduction for the Hyperbolic Space (2007)
Benjamini, Itai, Makarychev, Yury
A dimension reduction for the hyperbolic space is established. When points are far apart an embedding with bounded distortion into the hyperbolic plane is achieved.
Local global tradeoffs in metric embeddings (2007)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Suppose that every k points in a n point metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ1. This is...
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems (2007)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
In this paper we present approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1 − ε) satisfiable 2CSP our first...
Local global tradeoffs in metric embeddings (2007)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Suppose that every k points in a n point metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ1. This is...
Approximation Algorithm for the Max k-CSP Problem (2006)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
We present a ck 2k approximation algorithm for the Max k-CSP problem (where c> 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an...
How to play unique game using embeddings (2006)
Eden Chlamtac, Konstantin Makarychev, Yury Makarychev
In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states (labels), if a (1 − ε) fraction of all constraints is satisfiable, the...
Near-optimal algorithms for Unique Games (2006)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between...
How to play unique game using embeddings (2006)
Eden Chlamtac, Konstantin Makarychev, Yury Makarychev
In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states (labels), if a (1 − ε) fraction of all constraints is satisfiable, the...
Near-optimal algorithms for Unique Games (2006)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between...
Conditionally independent random variables (2005)
Makarychev, Konstantin, Makarychev, Yury
In this paper we investigate the notion of conditional independence and prove several information inequalities for conditionally independent random variables.
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
A new class of non-Shannon-type inequalities for entropies (2002)
Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai Vereshchagin
Abstract. In this paper we prove a countable set of non-Shannon-type linear information inequalities for entropies of discrete random variables, i.e., information inequalities which cannot be reduced...
A new class of non-Shannon-type inequalities for entropies (2002)
Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai Vereshchagin
Abstract. In this paper we prove a countable set of non-Shannon-type linear information inequalities for entropies of discrete random variables, i.e., information inequalities which cannot be reduced...
A short proof of Kuratowski’s graph planarity criterion (1997)
We present a new short combinatorial proof of the sufficiency part of the well-known Kuratowski's graph planarity criterion. The main steps are to prove that for a minor minimal non-planar graph...