|
| ||||||||||||||||||||||||||
Teaching
Spring 2013, Computational and Metric Geometry (TTIC 31100 and CMSC 37010-1).Winter 2012, Algorithms (TTIC 31010, CMSC 37000-1).
Fall 2010, Computational Geometry (TTIC 31100, CMSC 39000) (with Anastasios Sidiropoulos).
Publications
- "Bilu—Linial Stable Instances of Max Cut,"
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,
- preprint arXiv:1305.1681 [cs.DS], 2013.
- "Sorting Noisy Data with Partial Information,"
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,
- Innovations in Theoretical Computer Science, ITCS 2013 (to appear).
- "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.
- "The Grothendieck Constant is Strictly Smaller than Krivine's Bound,"
- Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor,
- FOCS 2011, pp. 453–462 ; 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, pp. 443–452 ; 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 Ω(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.
- "Balanced Allocation: Memory Performance Tradeoffs,"
- Itai Benjamini, Yury Makarychev,
- Annals of Applied Probability, vol. 22, no. 4, pp. 1642—1649, 2012.
- "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,
- Operations Research Letters, vol. 40, no. 6, pp. 450–452, 2012.
- "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).