Konstantin Makarychev

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.

Upcoming Talks

The 3rd Pacific Northwest Theory Day: http://www.pims.math.ca/scientific-event/130504-t3pntd

CSEDays — Theory 2013 in Yekaterinburg: http://www.csedays.ru/theory2013/about

Publications — Theory

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

Innovations in Theoretical Computer Science, ITCS 2013

 

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]

 

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; invited to the 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 3-spanners 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. 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 Ω(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,

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 2^{log1-ε 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

 

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/2^k 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/(2^k 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