Faculty Directory
Konstantin Makarychev

Professor of Computer Science

Contact

2233 Tech Drive
Mudd Room 3009
Evanston, IL 60208-3109

Email Konstantin Makarychev

Website

Konstantin Makarychev's Homepage


Departments

Computer Science


Download CV

Education

Ph.D. Computer Science, Princeton University, Princeton, NJ

B.S. Mechanics and Mathematics, Moscow State University, Moskva, Russia


Biography

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 worst-case analysis, and applications of high-dimension geometry to computer science.

Before joining Northwestern University, I was a researcher at Microsoft and IBM Research Labs. I obtained my PhD in Computer Science from Princeton University in 2007.

Research Interests

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 worst-case analysis, and applications of high-dimension geometry in computer science.


Selected Publications

Surveys and Book Chapters

Perturbation Resilience, Konstantin Makarychev and Yury Makarychev, Beyond the Worst-Case Analysis of Algorithms. Editor: Tim Roughgarden. Cambridge University Press. 2020. 

Approximation Algorithms for CSPs (a survey of results), Konstantin Makarychev and Yury Makarychev, The Constraint Satisfaction Problem: Complexity and Approximability. Editors: Andrei Krokhin and Stanislav Zivny. Dagstuhl Follow-Ups. 2017.

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. MIT Press. 2016.

Publications 

Explainable k-means. Don’t be greedy, plant bigger trees!, Konstantin Makarychev and Liren Shan, working paper

Near-optimal algorithms for explainable k-medians and k-means, Konstantin Makarychev and Liren Shan, ICML 2021

Local Correlation Clustering with Asymmetric Classification Errors, Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev, ICML 2021 

Batch Optimization for DNA Synthesis, Konstantin Makarychev, Miklos Z. Racz, Cyrus Rashtchian, Sergey Yekhanin, ISIT 2021

Two-sided Kirszbraun Theorem, Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, SoCG 2021

Improved Guarantees for k-means++ and k-means++ Parallel, Konstantin Makarychev, Aravind Reddy, Liren Shan, NeurIPS 2020

Correlation Clustering with Asymmetric Classification Errors, Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev, ICML 2020

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection, Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev, AISTATS 2020

Certified Algorithms: Worst-Case Analysis and Beyond, Konstantin Makarychev and Yury Makarychev, ITCS 2020, Correlation Clustering with Local Objectives, Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou, NeurIPS 2019

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering, Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn, STOC 2019

DNA assembly for nanopore data storage readout, with Karin Strauss, Luis Ceze, et al., Nature Communications 10, Article number: 2933 (2019)

Scaling up DNA data storage and random access retrieval, with Karin Strauss, Luis Ceze, et al., Nature Biotechnology 36, pp. 242-248, 2018

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

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, NeurIPS 2017 (spotlight presentation)

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

Robust algorithms with polynomial loss for near-unanimity 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 2016

A bi-criteria approximation algorithm for k-Means, 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

Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can, Virajith Jalaparti, Peter Bodik, Ishai Menache, Sriram Rao, Konstantin Makarychev, Matthew Caesar, SIGCOMM 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, A draft of the journal version is available here.

Precedence-constrained 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

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

Speed Regularization and Optimality in Word Classing, Geoffrey Zweig and Konstantin Makarychev, ICASSP 2013

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

Improved Approximation for the Directed Spanner Problem, 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

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability, 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, Konstantin Makarychev and Yury Makarychev, WAOA 2010, On Hardness of Pricing Items for Single-Minded Bidders, 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

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

ACM Transactions on Database Systems (TODS), vol. 35(4), pp. 25:1-25:37, IBM Pat Goldberg Best Paper Award

Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms, Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko, SODA 2008

Local Global Tradeoffs in Metric Embeddings, Moses Charikar, Konstantin Makarychev, Yury Makarychev, FOCS 2007, 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

Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems, Moses Charikar, Konstantin Makarychev, Yury Makarychev, SODA 2007; Special issue of ACM Transactions on Algorithms, vol. 5, no. 3, article 32, July 2009a

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, Eden Chlamtac, Konstantin Makarychev, Yury Makarychev, FOCS 2006

Near-Optimal Algorithms for Unique Games, Moses Charikar, Konstantin Makarychev, Yury Makarychev, STOC 2006

Directed Metrics and Directed Graph Partitioning Problems, Moses Charikar, Konstantin Makarychev, Yury Makarychev, SODA 2006

Square root log n approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems, Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev, STOC 2005

Quadratic Forms on Graphs, Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor, STOC 2005, 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, 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

PhD Thesis 

Quadratic Forms on Graphs and Their Applications,Konstantin Makarychev