  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

 Precedenceconstrained 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

 BiluLinial Stable Instances of Max Cut,

Konstantin Makarychev,
Yury Makarychev,
Aravindan Vijayaraghavan
 SODA 2014

 Approximation Algorithm for Sparsest kPartitioning,

Anand Louis and
Konstantin Makarychev
 SODA 2014

 Local Search is Better than Random Assignment for
Bounded Occurrence Ordering kCSPs,

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 NonBoolean MAX kCSP,

Konstantin Makarychev,
Yury Makarychev
 APPROX 2012

 Approximation Algorithms for Semirandom 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,

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 SemiRandom Adversary,

Alexandra Kolla,
Konstantin Makarychev,
Yury Makarychev
 FOCS 2011

 MinMax 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(n^{2/3}), due to Dinitz and Krauthgamer. We also improve the approximation ratio for the important special case of directed 3spanners with unit edge
lengths from O(√n) to O(n^{1/3} log n).
Piotr Berman,
Arnab Bhattacharyya,
Konstantin Makarychev,
Sofya Raskhodnikova,
Grigory Yaroslavtsev
 ICALP 2011; Special Issue of Information and Computation, vol. 222, pp. 93107, 2013.

 Maximizing Polynomials Subject to Assignment Constraints,

Konstantin Makarychev and
Maxim Sviridenko,
 ICALP 2011

 On Parsimonious Explanations For 2D Tree and LinearlyOrdered Data,

Howard Karloff,
Flip Korn,
Konstantin Makarychev,
Yuval Rabani
 STACS 2011

 Assembly of Circular Genomes,

Konstantin Makarychev and
Alantha Newman
 ITCS 2011, pp. 444459

 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 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.
Konstantin Makarychev and
Yury Makarychev
 FOCS 2010

 Maximum Quadratic Assignment Problem,

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 SingleMinded 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 APXhard (Guruswami et al). The best known
approximation algorithm, by Balcan and Blum, gives a 4approximation. 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 NPhard to approximate within a factor
of 2 assuming the Unique Games Conjecture; and it is unconditionally NPhard to approximate
within a factor 17/16. Finally, we extend the APXhardness 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 SheraliAdams Relaxations,

Moses Charikar,
Konstantin Makarychev,
Yury Makarychev,
 STOC 2009, pp. 283292

 Online MaketoOrder Joint Replenishment Model: Primal Dual Competitive Algorithms,

Niv Buchbinder,
Tracy Kimbrel,
Retsef Levi,
Konstantin Makarychev,
Maxim Sviridenko,
 SODA 2008, pp. 952961

 Local Global Tradeoffs in Metric Embeddings,

Moses Charikar,
Konstantin Makarychev,
Yury Makarychev,
 FOCS 2007, pp. 713723;
 Special issue of SIAM Journal of Computing (SICOMP), vol. 39, no. 6, pp. 24872512, 2010

 On the Advantage over Random for Maximum Acyclic Subgraph,

Moses Charikar,
Konstantin Makarychev,
Yury Makarychev,
 FOCS 2007, pp. 625633


NearOptimal Algorithms for Maximum Constraint Satisfaction Problems,

Moses Charikar,
Konstantin Makarychev,
Yury Makarychev,
 SODA 2007, pp. 6268;
 Special issue of ACM Transactions on Algorithms, vol. 5, no. 3, article 32, July 2009

 A Divide and Conquer Algorithm for dDimensional Linear Arrangement,

Moses Charikar,
Konstantin Makarychev,
Yury Makarychev,
 SODA 2007

 How to Play Unique Games Using Embeddings,

Eden Chlamtac,
Konstantin Makarychev,
Yury Makarychev,
 FOCS 2006, pp. 687696

 NearOptimal 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. 205214

 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. 5160

 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. 573581

 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. 486493;

Inventiones Mathematicae, vol. 163, no. 3, pp. 499522, March 2006

 Chain Independence and Common Information,

Konstantin Makarychev and
Yury Makarychev
 IEEE Transactions on Information Theory, 58(8), pp. 52795286, 2012

 A new class of non Shannon type inequalities for entropies,

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 Zhang
and Yeung who found the first examples of nonShannontype information inequalities.
Konstantin Makarychev,
Yury Makarychev,
Andrei Romashchenko,
Nikolai Vereshchagin
 Communications in
Information and Systems, vol. 2, no. 2, pp. 147166, 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
Ttetrominoes (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. 827840
 ACM Transactions on Database Systems (TODS), vol. 35(4), pp. 25:125:37
 IBM Pat Goldberg Best Paper Award

PhD Thesis
Quadratic Forms on Graphs
and
Their Applications,
Konstantin Makarychev
