Yury Makarychev   Assistant Professor, Toyota Technological Institute at Chicago (TTIC).   Assistant Professor (part time), Department of Computer Science, University of Chicago.     Ph.D. in Computer Science, Princeton University. My advisor was Moses Charikar.   M.S. in Mathematics, Moscow State University.   Finished Moscow Math High School #57.       Contact Information   TTIC   6045 S. Kenwood Ave.   Chicago, IL 60637   e-mail: yurdu

Teaching

Publications

"Approximation Algorithms for Semi-random Graph Partitioning Problems,"

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,

STOC 2012 (to appear).

 

"Approximation Algorithms and Hardness of the k-Route Cut Problem,"

Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou,

SODA 2012.

 

"The Grothendieck Constant is Strictly Smaller than Krivine's Bound,"

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor,

FOCS 2011; preprint arXiv:1103.6161 [math.FA], 2011.

 

"How to Play Unique Games Against a Semi-Random Adversary,"

Alexandra Kolla, Konstantin Makarychev, Yury Makarychev,

FOCS 2011; preprint arXiv:1104.3806 [cs.DS], 2011.

 

"Finding Almost-perfect Graph Bisections,"

Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou,

Innovations in Computer Science, ICS 2011, pp. 321-337.

 

"On Graph Crossing Number and Edge Planarization,"

Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos,

SODA 2011, pp. 1050-1069.

 

"Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability,"

Konstantin Makarychev, Yury Makarychev,

FOCS 2010, pp. 255-264.

We study vertex cut and flow sparsifiers that were recently introduced by Moitra, and Leighton and Moitra. We give a new polynomial-time algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best known existential upper bound. We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1950s. Using this connection, we prove a lower bound of Ω(log k/log log k)^1/2 for flow sparsifiers and a lower bound of Ω(log^1/2 k/log log k) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist ~O(log k)^1/2 cut sparsifiers.

 

"Subgraph Sparsification and Nearly Optimal Ultrasparsifiers,"

Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng,

STOC 2010, pp. 57-65.

 

"How to Play Unique Games on Expanders,"

Konstantin Makarychev, Yury Makarychev,

WAOA 2010, Lecture Notes in Computer Science, vol. 6534/2011, pp. 190-200, 2011.

 

"Balanced Allocation: Memory Performance Tradeoffs,"

Itai Benjamini, Yury Makarychev,

Annals of Applied Probability (to appear).

 

"Eigenvalue multiplicity and volume growth,"

James R. Lee, Yury Makarychev,

Journal of Topology and Analysis (to appear).

 

"Simple Linear Time Approximation Algorithm for Betweenness,"

Yury Makarychev,

Microsoft Research Technical Report MSR-TR-2009-74.

 

"Integrality Gaps for Sherali-Adams Relaxations,"

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

STOC 2009, pp. 283-292.

 

"Dimension Reduction for the Hyperbolic Space,"

Itai Benjamini, Yury Makarychev,

Proc. Amer. Math. Soc. 137 (2009), pp. 695-698.

 

"Local Global Tradeoffs in Metric Embeddings,"

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

FOCS 2007, pp. 713-723,

Special issue of SIAM J.Comput. (SICOMP), vol. 39, no. 6, pp. 2487-2512, 2010.

Suppose we are given a metric space X such that every k points in X are D-distortion embeddable into l₁. In this paper, we study with which distortion the entire space X embeds into l₁.

 

"On the Advantage over Random for Maximum Acyclic Subgraph,"

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

FOCS 2007, pp. 625-633.

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 finds an acyclic subgraph with 1/2 + Ω(δ/ log n) fraction of all edges.

 

"Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems,"

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

SODA 2007, pp. 62-68,

Special issue of ACM Transactions on Algorithms, vol. 5, no. 3, July 2009.

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 algorithm finds an assignment of variables satisfying a 1 - O(sqrt{ε}) fraction of all constraints. The best previously known result, due to Zwick, was 1 - O(ε^1/3).
The second algorithm finds a ck/2^k approximation 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 had an approximation guarantee of Ω(k/(2^k log k)).

 

"A Divide and Conquer Algorithm for d-Dimensional Arrangement,"

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

SODA 2007, pp. 541-546.

 

"How to Play Unique Games Using Embeddings,"

Eden Chlamtac, Konstantin Makarychev, Yury Makarychev,

FOCS 2006, pp. 687-696.

In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states, if a (1 - ε) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1-O(ε(log n log k)^1/2) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.

 

"Near-Optimal Algorithms for Unique Games,"

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

STOC 2006, pp. 205-214.

We present approximation algorithms for unique games. For instances with domain size k where the optimal solution satisfies 1 - ε fraction of all constraints, our algorithms satisfy roughly k^{-ε/(2 - ε)} and 1 - O(ε log k) fraction of all constraints. Our algorithms are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. Our results are near-optimal if the Unique Games Conjecture is true, i.e. any improvement (beyond low order terms) would refute the conjecture.

 

"Directed Metrics and Directed Graph Partitioning Problems,"

Moses Charikar, Konstantin Makarychev, Yury Makarychev,

SODA 2006, pp. 51-60.

 

"O(sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems,"

Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev,

STOC 2005, pp. 573-581.

We give O(sqrt{log n})-approximation algorithms for the Min UnCut, Min 2CNF Deletion, Directed Balanced Separator, and Directed Sparsest Cut problems. The previously best known algorithms give an O(log n)-approximation for Min UnCut, Directed Balanced Separator, Directed Sparsest Cut, and an O(log n log log n)-approximation for Min 2CNF Deletion.
We also show that the integrality gap of an SDP relaxation of the Minimum Multicut problem is Ω(log n).

 

"Quadratic forms on graphs,"

Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor,

STOC 2005, pp. 586-493,

Inventiones Mathematicae, vol. 163, no. 3, pp. 499-522, 2006.

We introduce a new graph parameter, called the Grothendieck constant of a graph. This parameter is a generalization of the classical Grothendieck constant; and it is equal to an integrality gap of a certain SDP problem, which has various algorithmic applications. Our results improve a recent result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settle a problem of Megretski and of Charikar and Wirth.

 

"Conditionally Independent Random Variables,"

Konstantin Makarychev, Yury Makarychev,

Technical Report arXiv:cs.IT/0510029.

In this paper we investigate the notion of conditional independence and prove several information inequalities for conditionally independent random variables.

 

"A new class of non Shannon type inequalities for entropies,"

K. Makarychev, Y. Makarychev, A. Romashchenko, N. Vereshchagin,

Communications in Information and Systems, vol. 2, no. 2, pp. 147-166, December 2002.

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 to the "basic" inequality I(X : Y |Z) > 0. Our results generalize the inequalities of Z. Zhang and R. Yeung (1998) who found the first examples of non-Shannon-type information inequalities.

 

"The Importance of Being Formal,"

Konstantin Makarychev, Yury Makarychev,

The Mathematical Intelligencer, vol. 23 no. 1, 2001.

 

"A Short Proof of Kuratowski's Graph Planarity Criterion,"

Yury Makarychev,

The Journal of Graph Theory, vol. 25, pp. 129-131, 1997.

We present a new short combinatorial proof of the well-known Kuratowski's graph planarity criterion.

 

"Proof of Pak's conjecture on tilings by T-tetrominoes" (in Russian)

Konstantin Makarychev, Yury Makarychev,

Manuscript.

We prove the conjecture from Igor Pak's paper "The Invariants: New Horizons". The conjecture states that any tiling of a rectangle by T-tetrominoes can be transformed to any other tiling by a series of "local moves". We also show connections between this problem and the "six-vertex model" (studied in mathematical physics).