My Picture

Yury Makarychev

 I am an Associate Professor at the Toyota Technological Institute at Chicago (TTIC). I also hold a part-time appointment at the Department of Computer Science, University of Chicago.
 
 I did my Ph.D. in Computer Science at Princeton University under supervision of Moses Charikar. I received my undergraduate degree from the Deparment of Mathematics, Moscow State University. I finished Moscow Math High School #57.
  
 Contact Information
 TTIC
 6045 S. Kenwood Ave.
 Chicago, IL 60637
 e-mail: yurdu

Teaching

Programming Requirement at TTIC (online presentation).

Summer 2014, REU: Semidefinite Programming and Constraint Satisfaction (with Madhur Tulsiani).
Winter 2014, Algorithms (TTIC 31010).
Spring 2013, Computational and Metric Geometry (TTIC 31100 and CMSC 39010-1).
Winter 2012, Algorithms (TTIC 31010, CMSC 37000-1).
Fall 2010, Computational Geometry (TTIC 31100, CMSC 39000) (with Anastasios Sidiropoulos).

Publications

"Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion,"
Anand Louis, Yury Makarychev,
APPROX 2014 (to appear).
 
"Nonuniform Graph Partitioning with Unrelated Weights,"
Konstantin Makarychev, Yury Makarychev,
ICALP 2014.
 
"Constant Factor Approximation for Balanced Cut in the PIE Model,"
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,
STOC 2014.
 
"Bilu—Linial Stable Instances of Max Cut and Minimum Multiway Cut,"
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,
SODA 2014.
 
"Clustering, Hamming Embedding, Generalized LSH and the Max Norm,"
Behnam Neyshabur, Yury Makarychev, Nathan Srebro,
ALT 2014 (to appear).
 
"A pseudo-approximation for the genus of Hamiltonian graphs,"
Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos,
APPROX 2013.
 
"The Power of Asymmetry in Binary Hashing,"
Behnam Neyshabur, Payman Yadollahpour, Yury Makarychev, Ruslan Salakhutdinov, Nathan Srebro
NIPS 2013.
 
"Sorting Noisy Data with Partial Information,"
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,
Innovations in Theoretical Computer Science, ITCS 2013.
 
"Approximation Algorithm for Non-Boolean MAX k-CSP,"
Konstantin Makarychev, Yury Makarychev,
APPROX 2012, pp. 254—265.
 
"Planarizing an Unknown Surface,"
Yury Makarychev, Anastasios Sidiropoulos,
APPROX 2012, pp. 266—275.
 
"Approximation Algorithms for Semi-random Graph Partitioning Problems,"
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,
STOC 2012, pp. 367–384.
 
"Approximation Algorithms and Hardness of the k-Route Cut Problem,"
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou,
SODA 2012, pp. 780–799.
 
"Simple Linear Time Approximation Algorithm for Betweenness,"
Yury Makarychev,
Operations Research Letters, vol. 40, no. 6, pp. 450–452, 2012.
 
"Balanced Allocation: Memory Performance Tradeoffs,"
Itai Benjamini, Yury Makarychev,
Annals of Applied Probability, vol. 22, no. 4, pp. 1642—1649, 2012.
 
"The Grothendieck Constant is Strictly Smaller than Krivine's Bound,"
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor,
FOCS 2011, pp. 453–462;
Forum of Mathematics, Pi, vol. 1, e4, 2013.
 
"How to Play Unique Games Against a Semi-Random Adversary,"
Alexandra Kolla, Konstantin Makarychev, Yury Makarychev,
FOCS 2011, pp. 443–452.
 
"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 Ω(log1/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.
 
"Eigenvalue multiplicity and volume growth,"
James R. Lee, Yury Makarychev,
Journal of Topology and Analysis (to appear).
 
"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 l1. In this paper, we study with which distortion the entire space X embeds into l1.
 
"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/2k 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/(2k 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.
 
"Chain Independent Random Variables and Common Information,"
Konstantin Makarychev, Yury Makarychev,
IEEE Transactions on Information Theory, 58(8), pp. 5279–5286, 2012.
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).