Yury Makarychev

Yury Makarychev
	I am a postdoctoral researcher in the Theory Group at Microsoft Research.
	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.
	e-mail: ymakaryc@cs_•princeton_•edu

FOCS'08 Call For Papers

Computer Science Symposium in Russia'08

Publications

"Integrality Gaps for Sherali-Adams Relaxations,": Moses Charikar, Konstantin Makarychev, Yury Makarychev,; manuscript, 2007.
"Local Global Tradeoffs in Metric Embeddings,": Moses Charikar, Konstantin Makarychev, Yury Makarychev,; FOCS 2007,; Suppose that every k points in a n point metric space X are D-distortion embeddable into l₁. We give upper and lower bounds on the distortion required to embed the entire space X into l₁.
"On the Advantage over Random for Maximum Acyclic Subgraph,": Moses Charikar, Konstantin Makarychev, Yury Makarychev,; FOCS 2007,; 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.
Dimension Reduction for the Hyperbolic Space,: Itai Benjamini, Yury Makarychev,; preprint, arXiv:0710.1343v1 [math.MG].
"Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems,": Moses Charikar, Konstantin Makarychev, Yury Makarychev,; SODA 2007,; Preliminary version appeared in two technical reports: ECCC Technical Report TR06-063, ECCC Technical Report TR06-064,; 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)).
Both results are optimal assuming the Unique Games Conjecture and are based on rounding natural semidefinite programming relaxations. We also believe that our algorithms and their analysis are simpler than those previously known.
"A Divide and Conquer Algorithm for d-Dimensional Arrangement,": Moses Charikar, Konstantin Makarychev, Yury Makarychev,; SODA 2007.
"How to Play Unique Game Using Embeddings,": Eden Chlamtac, Konstantin Makarychev, Yury Makarychev,; FOCS 2006,; 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,; 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.
"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,; 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,; 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).
The problem was independently solved in "Tilings of rectangles with T-tetrominoes" by Michael Korn and Igor Pak.