Photo  

Konstantin Makarychev

I am a researcher at Microsoft Research in the Theory group. My area of research is algorithms and theoretical computer science.

I graduated from Princeton University in 2007. My advisor was Moses Charikar. Before attending Princeton I was an undergraduate student at the Mathematics Department of Moscow State University. I finished Moscow Math High School #57.

Publications — Theory

Optimization Problems with Diseconomies of Scale,
Konstantin Makarychev and Maxim Sviridenko
manuscript
 
Nonuniform Graph Partitioning with Unrelated Weights,
Konstantin Makarychev and Yury Makarychev
to appear at ICALP 2014
 
Precedence-constrained Scheduling of Malleable Jobs with Preemption,
Konstantin Makarychev and Debmalya Panigrahi
to appear at ICALP 2014
 
Constant Factor Approximation for Balanced Cut in the PIE Model,
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
to appear in STOC 2014
 
Bilu-Linial Stable Instances of Max Cut,
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
SODA 2014
 
Approximation Algorithm for Sparsest k-Partitioning,
Anand Louis and Konstantin Makarychev
SODA 2014
 
Local Search is Better than Random Assignment for
Bounded Occurrence Ordering k-CSPs,
Konstantin Makarychev
STACS 2013
 
Sorting Noisy Data with Partial Information,
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
ITCS 2013 – Innovations in Theoretical Computer Science
 
Approximation Algorithm for Non-Boolean MAX k-CSP,
Konstantin Makarychev, Yury Makarychev
APPROX 2012
 
Approximation Algorithms for Semi-random Graph Partitioning Problems,
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
STOC 2012
 
Concentration Inequalities for Nonlinear Matroid Intersection,
Konstantin Makarychev, Warren Schudy, Maxim Sviridenko
SODA 2012
 
The Grothendieck Constant is Strictly Smaller than Krivine's Bound,
We prove that the Grothendieck constant is strictly smaller than Krivine's bound. The Grothendieck constant equals to the integrality gap of the natural SPD relaxation for the integer quadratic program

maximize ∑ A_ij x_i y_j, where x_i, y_j∈{±1}.

Krivine's upper bound equals π ⁄ (2 log(1 + √2)).
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
FOCS 2011; preprint arXiv:1103.6161 [math.FA]
Forum of Mathematics, Π, Volume 1, 2013
 
How to Play Unique Games Against a Semi-Random Adversary,
We study the average case complexity of the Unique Games problem. We propose a natural semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an ε-fraction of all edges, and finally replaces ("corrupts") the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1-ε) satisfiable instance, so then the problem is as hard as in the worst case. In our semi-random model, one of the steps is random, and all other steps are adversarial. We show that known algorithms for unique games (in particular, all algorithms that use the standard SDP relaxation) fail to solve semi-random instances of Unique Games.

We present an algorithm that with high probability finds a solution satisfying a (1-δ) fraction of all constraints in semi-random instances (we require that the average degree of the graph is Ω(log k). To this end, we consider a new non-standard SDP program for Unique Games, which is not a relaxation for the problem, and show how to analyze it. We present a new rounding scheme that simultaneously uses SDP and LP solutions, which we believe is of independent interest.

Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
FOCS 2011
 
Min-Max Graph Partitioning and Small Set Expansion,
Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, Roy Schwartz
FOCS 2011; Special Issue of SIAM Journal of Computing (SICOMP)
 
Improved Approximation for the Directed Spanner Problem,
We present an O(√n log n)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. The previous best approximation ratio was (ignoring logarithmic factors) O(n2/3), due to Dinitz and Krauthgamer. We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from O(√n) to O(n1/3 log n).
Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
ICALP 2011; Special Issue of Information and Computation, vol. 222, pp. 93-107, 2013.
 
Maximizing Polynomials Subject to Assignment Constraints,
Konstantin Makarychev and Maxim Sviridenko,
ICALP 2011
 
On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data,
Howard Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
STACS 2011
 
Assembly of Circular Genomes,
Konstantin Makarychev and Alantha Newman
ITCS 2011, pp. 444-459
 
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability,
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.
Konstantin Makarychev and Yury Makarychev
FOCS 2010
 
Maximum Quadratic Assignment Problem,
We study the maximum quadratic problem: given two weighted graphs G and H on n vertices, find a bijective mapping of vertices of G to vertices of H so as to maximize the number of edges of G mapped to edges of H. More precisely, given two sets of weights a(u,v) and b(p,q) for u,v,p,q ∈ [n], the goal is to find a permutation π to maximize ∑ a(u,v) b (π(u), π(v)).

We show that for every positive ε unless NP⊂BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log1-ε n by a reduction from the maximum label cover problem. Then, we present an O(√ n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.

Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko,
ICALP 2010; accepted to ACM Transactions on Algorithms
 
How to Play Unique Games on Expanders,
In this paper, we improve a result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a (1-ε)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignment satisfying at least a (1- C ε h(G)) fraction of all constraints if ε < c λ(G) where h(G) is the edge expansion of G, λ(G) is the second smallest eigenvalue of the Laplacian of G, and C and c are some absolute constants.
Konstantin Makarychev and Yury Makarychev
WAOA 2010
 
On Hardness of Pricing Items for Single-Minded Bidders,
We consider the following item pricing problem: A seller has an infinite numbers of copies of n items. There are m buyers, each with a budget and an intention to buy a fixed subset of items. Given prices on the items, each buyer buys his subset of items, at the given prices, provided the total price of the subset is at most his budget. The objective of the seller is to determine the prices such that her total profit is maximized. In this paper, we focus on the case where the buyers are interested in subsets of size at most two. This special case is known to be APX-hard (Guruswami et al). The best known approximation algorithm, by Balcan and Blum, gives a 4-approximation. We show that there is indeed a gap of 4 for the combinatorial upper bound used in their analysis. We further show that a natural linear programming relaxation of this problem has an integrality gap of 4, even in this special case. Then we prove that the problem is NP-hard to approximate within a factor of 2 assuming the Unique Games Conjecture; and it is unconditionally NP-hard to approximate within a factor 17/16. Finally, we extend the APX-hardness of the problem to the special case in which the graph formed by items as vertices and buyers as edges is bipartite. We hope that our techniques will be helpful for obtaining stronger hardness of approximation bounds for this problem.
Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko,
APPROX 2009 (see a nice entry on the problem at Richard Lipton's blog).
 
Integrality Gaps for Sherali-Adams Relaxations,
Moses Charikar, Konstantin Makarychev, Yury Makarychev,
STOC 2009, pp. 283-292
 
Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms,
Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko,
SODA 2008, pp. 952-961
 
Local Global Tradeoffs in Metric Embeddings,
Moses Charikar, Konstantin Makarychev, Yury Makarychev,
FOCS 2007, pp. 713-723;
Special issue of SIAM Journal of Computing (SICOMP), vol. 39, no. 6, pp. 2487-2512, 2010
 
On the Advantage over Random for Maximum Acyclic Subgraph,
Moses Charikar, Konstantin Makarychev, Yury Makarychev,
FOCS 2007, pp. 625-633
 
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems,
In this paper we study two Maximum Constraint Satisfaction Problems: MAX 2SAT and MAX k-CSP.

For MAX 2SAT, we present an approximation algorithm that given a (1-ε) satisfiable instance finds an assignment of variables satisfying a 1-O(ε) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture. The best previously known result, due to Zwick, was 1-O(ε1/3)

For MAX k-CSP, we present a ck/2k approximation algorithm (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of   Ω(k/(2k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up to a constant factor (their result assumes the Unique Games Conjecture).

Moses Charikar, Konstantin Makarychev, Yury Makarychev,
SODA 2007, pp. 62-68;
Special issue of ACM Transactions on Algorithms, vol. 5, no. 3, article 32, July 2009
 
A Divide and Conquer Algorithm for d-Dimensional Linear Arrangement,
Moses Charikar, Konstantin Makarychev, Yury Makarychev,
SODA 2007
 
How to Play Unique Games Using Embeddings,
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))

fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.
Eden Chlamtac, Konstantin Makarychev, Yury Makarychev,
FOCS 2006, pp. 687-696
 
Near-Optimal Algorithms for Unique Games,
We present approximation algorithms for the Unique Game Problem. For instances with domain size k where the optimal solution satisfies (1 - ε) fraction of all constraints, our algorithms satisfy roughly k-½ ε and 1 - O((ε log k)½) fraction of all constraints. Our results are near optimal if the Unique Games Conjecture is true.
Moses Charikar, Konstantin Makarychev, Yury Makarychev,
STOC 2006, pp. 205-214
 
Directed Metrics and Directed Graph Partitioning Problems,
In this paper we initiate a study of metric embeddings for directed metrics and their applications to directed partitioning problems. We prove low and upper bounds for the distortion of such embeddings.
Moses Charikar, Konstantin Makarychev, Yury Makarychev,
SODA 2006, pp. 51-60
 
Square root log n approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems,
We give O(√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).
Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev,
STOC 2005, pp. 573-581
 
Quadratic Forms on Graphs,
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 the 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.
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
STOC 2005, pp. 486-493;
Inventiones Mathematicae, vol. 163, no. 3, pp. 499-522, March 2006
 
Chain Independence and Common Information,
Konstantin Makarychev and Yury Makarychev
IEEE Transactions on Information Theory, 58(8), pp. 5279-5286, 2012
 
A new class of non Shannon type inequalities for entropies,
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 Zhang and Yeung who found the first examples of non-Shannon-type information inequalities.
Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai Vereshchagin
Communications in Information and Systems, vol. 2, no. 2, pp. 147-166, December 2002
 
The Importance of Being Formal,
Konstantin Makarychev and Yury Makarychev
The Mathematical Intelligencer, vol. 23 no. 1, 2001
 
Proof of Pak's conjecture on tilings by T-tetrominoes (in Russian),
Konstantin Makarychev and Yury Makarychev
manuscript
 

Publications — Applied CS

Speed Regularization and Optimality in Word Classing
Geoffrey Zweig and Konstantin Makarychev
ICASSP 2013
 
Indexing Genomic Sequences on the IBM Blue Gene,
Amol Ghoting and Konstantin Makarychev
SC 2009
ACM Gordon Bell Prize Finalist
 
Serial and Parallel Methods for I/O Efficient Suffix Tree Construction,
Amol Ghoting and Konstantin Makarychev
SIGMOD 2009, pp. 827-840
ACM Transactions on Database Systems (TODS), vol. 35(4), pp. 25:1-25:37
IBM Pat Goldberg Best Paper Award
 

PhD Thesis

 Quadratic Forms on Graphs and Their Applications,
Konstantin Makarychev