
Teaching
Programming Requirement at TTIC (online presentation).
Winter 2015, Computational and Metric Geometry (TTIC 31100 and CMSC 390101).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 390101).
Winter 2012, Algorithms (TTIC 31010, CMSC 370001).
Fall 2010, Computational Geometry (TTIC 31100, CMSC 39000) (with Anastasios Sidiropoulos).
I advise Haris Angelidakis.
Publications
 Satisfiability of Ordering CSPs Above Average,
 Konstantin Makarychev, Yury Makarychev, Yuan Zhou,
 arXiv:1503.03851 [cs.DS]
 Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion,
 Anand Louis, Yury Makarychev,
 APPROX 2014.
 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.
 A pseudoapproximation 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 NonBoolean MAX kCSP,
 Konstantin Makarychev, Yury Makarychev,
 APPROX 2012, pp. 254—265;
 Theory of Computing, Volume 10 (2014), Article 13, pp. 341—358.
 Planarizing an Unknown Surface,
 Yury Makarychev, Anastasios Sidiropoulos,
 APPROX 2012, pp. 266—275.
 Approximation Algorithms for Semirandom Graph Partitioning Problems,
 Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,
 STOC 2012, pp. 367–384.
 Approximation Algorithms and Hardness of the kRoute 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 SemiRandom Adversary,
 Alexandra Kolla, Konstantin Makarychev, Yury Makarychev,
 FOCS 2011, pp. 443–452.
 Finding Almostperfect 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.
 Israel Journal of Mathematics (to appear).
 We study vertex cut and flow sparsifiers that were recently introduced by Moitra, and Leighton and Moitra. We give a new polynomialtime 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, ShangHua 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 SheraliAdams 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 Ddistortion embeddable into l_{1}. In this paper, we study with which distortion the entire space X embeds into l_{1}.
 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.
 NearOptimal 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 kCSP).
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 kCSP 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 dDimensional 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 1O(ε(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.
 NearOptimal 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 nearoptimal 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 nonShannontype 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 nonShannontype 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 wellknown Kuratowski's graph planarity criterion.
 Proof of Pak's conjecture on tilings by Ttetrominoes (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 Ttetrominoes can be transformed to any other tiling by a series of "local moves". We also show connections between this problem and the "sixvertex model" (studied in mathematical physics).