  Konstantin Makarychev
I am an Associate Professor of Computer Science at Northwestern University. I am interested in designing efficient algorithms for computationally hard problems. The aim of my research is to introduce new core techniques and design general principles for developing and analyzing algorithms that work in theory and practice. My research interests include approximation algorithms, beyond worstcase analysis, and applications of highdimension geometry in computer science.
Before joining Northwestern, I was a researcher at Microsoft and IBM Research Labs. I graduated from Princeton University in 2007. My PhD advisor was
Moses Charikar. I received my undergraduate degree at the Department of Mathematics
at Moscow State University. I finished Moscow Math High School #57.
Teaching
 Northwestern University, Winter 2018: Design and Analysis of Algorithms
 Northwestern University, Spring 2017: Course on Approximation Algorithms
Workshops
 Northwestern University, May 2425, 2017: Workshop on Beyond Worst Case Analysis
Surveys
 Approximation Algorithms for CSPs (a survey of results),
 Konstantin Makarychev and
Yury Makarychev
 The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Zivny (Eds.), Dagstuhl FollowUps.

 Bilu–Linial Stability (a survey on Bilu–Linial stability and perturbation resilience),
 Konstantin Makarychev and
Yury Makarychev
 Advanced Structured Prediction. Editors: T. Hazan, G. Papandreou, D. Tarlow (Eds.). MIT Press, 2016.
 You can download a draft copy of the survey here.

Publications — Theory
 Performance of JohnsonLindenstrauss Transform for kMeans and kMedians Clustering,
 Konstantin Makarychev,
Yury Makarychev,
Ilya Razenshteyn
 STOC 2019, to appear

 Nonlinear Dimension Reduction via Outer BiLipschitz Extensions,
 Sepideh Mahabadi,
Konstantin Makarychev,
Yury Makarychev,
Ilya Razenshteyn
 STOC 2018

 Algorithms for Stable and PerturbationResilient Problems,
 Haris Angelidakis, Konstantin Makarychev,
Yury Makarychev
 The first part of the paper is available at http://arxiv.org/abs/1607.06442.
The full version of the paper will be soon posted on arxiv.
 STOC 2017

 Robust algorithms with polynomial loss for nearunanimity CSPs,
 Victor Dalmau,
Marcin Kozik,
Andrei Krokhin,
Konstantin Makarychev,
Yury Makarychev,
Jakub Opršal
 SODA 2017

 Learning Communities in the Presence of Errors,

Konstantin Makarychev,
Yury Makarychev,
Aravindan Vijayaraghavan
 COLT 2016

 Union of Euclidean Metric Spaces is Euclidean,
 Konstantin Makarychev and
Yury Makarychev
 Discrete Analysis

 A bicriteria approximation algorithm for kMeans,
 Konstantin Makarychev,
Yury Makarychev,
Maxim Sviridenko,
Justin Ward
 APPROX 2016

 Satisfiability of Ordering CSPs Above Average,
 Konstantin Makarychev,
Yury Makarychev,
Yuan Zhou
 FOCS 2015

 Correlation Clustering with Noisy Partial Information,

Konstantin Makarychev,
Yury Makarychev,
Aravindan Vijayaraghavan
 COLT 2015

 Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete Graphs,

Shuchi Chawla,
Konstantin Makarychev,
Tselil Schramm,
Grigory Yaroslavtsev
 STOC 2015

 Solving Optimization Problems with Diseconomies of Scale,

Konstantin Makarychev and
Maxim Sviridenko
 FOCS 2014
 Journal of the ACM, Volume 65, Issue 6, November 2018, Article No. 42.

 Nonuniform Graph Partitioning with Unrelated Weights,
 Konstantin Makarychev and Yury Makarychev
 ICALP 2014
 Sbornik: Mathematics (Russian Academy of Sciences), vol. 208, 2017.
 A draft of the journal version is available here.

 Precedenceconstrained Scheduling of Malleable Jobs with Preemption,
 Konstantin Makarychev and Debmalya Panigrahi
 ICALP 2014

 Constant Factor Approximation for Balanced Cut in the PIE Model,

Konstantin Makarychev,
Yury Makarychev,
Aravindan Vijayaraghavan
 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 and
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
 Random Structures & Algorithms, vol. 46, no. 3, 2015

 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), vol. 43, no. 2, 2014
 Journal version is available here.

 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;
 Israel Journal of Mathematics, vol. 212 (2), May 2016

 Maximum Quadratic Assignment Problem,

Konstantin Makarychev,
Rajsekar Manokaran,
Maxim Sviridenko,
 ICALP 2010
 ACM Transactions on Algorithms, vol. 10, no. 4, article 18, August 2014

 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
 Clustering Billions of Reads for DNA Data Storage
 Cyrus Rashtchian,
Konstantin Makarychev,
Miklos Z. Racz,
Siena Dumas Ang,
Djordje Jevdjic,
Sergey Yekhanin,
Luis Ceze,
Karin Strauss
 NIPS 2017 (spotlight presentation)

 Scaling up DNA data storage and random access retrieval
 with Karin Strauss,
Luis Ceze et al.
 to appear in Nature Biotechnology, 2018

 NetworkAware Scheduling for DataParallel Jobs: Plan When You Can
 Virajith Jalaparti,
Peter Bodik,
Ishai Menache,
Sriram Rao,
Konstantin Makarychev,
Matthew Caesar
 SIGCOMM 2015

 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

