About me
I am a 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 worst-case analysis, theory of machine learning, and applications of high-dimension 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.
See my CV in html or pdf format for more info.
You can find my video lectures as well as video recordings from workshops I recently organized with Yury Makarychev on my Youtube channel @AdvancedAlgorithms.
Events at Northwestern
- May 27, 2022: IDEAL Workshop on High-Dimensional Analysis and Geometry
- May 13, 2022: IDEAL Workshop on Algorithms for Massive Data Sets
- April 22-23, 2022: IDEAL Workshop on Clustering
- November 14-15, 2019: 2019 Junior Theorists Workshop
- May 24-25, 2019: CS+Math Workshop on Metric Embeddings and Dimensionality Reduction
- May 24-25, 2017: Workshop on Beyond Worst Case Analysis
PhD Program
- If you are interested in algorithms and theoretical computer science, we encourage you to apply to the PhD program at Northwestern University (more info).
Talks
- Tomsk University (remote; YouTube), February 15, 2022: Explainable k-means. Don’t be greedy, plant bigger trees!
- Yahoo! Research (remote), May 29, 2020: Correlation Clustering
- Tel Aviv University, December 9, 2019: Dimensionality Reduction for k-Means and k-Medians Clustering
- Technion, December 2, 2019: Dimensionality Reduction for k-Means and k-Medians Clustering
- Illinois Institute of Technology, November 19, 2019: Dimensionality Reduction for k-Means and k-Medians Clustering
- FOCS Workshop on Beyond the Worst Case Analysis of Algorithms, November 9, 2019: Perturbation Stability and Certified Algorithms
- UPenn, October 25, 2019: Dimensionality Reduction for k-Means and k-Medians Clustering
- TTIC Workshop on Recent Trends in Clustering, September 18, 2019: Correlation Clustering
Teaching
Northwestern University
- Design and Analysis of Algorithms: Winter 2024, Fall 2022, Fall 2021, Winter 2021, Winter 2020, Winter 2019, Spring 2018, Winter 2018
- Graduate Algorithms (syllabus): Fall 2024, Spring 2024, Fall 2020, Spring 2020
- Approximation Algorithms (syllabus): Fall 2024, Winter 2023, Winter 2021, Spring 2019, Spring 2017
- Special Topics in Approximation Algorithms: Winter 2025, Spring 2020
- Advanced Algorithm Design Through the Lens of Competitive Programming: Winter 2022
- Algorithms for Big Data: Spring 2022
- Math Toolkit for Theoretical Computer Scientists: Spring 2019
University of Washington
- Linear and Semi-Definite Programming in Approximation Algorithms (with Mohit Singh): Fall 2014
Current and Former PhD Students
- Dionysios Arvanitakis (co-advised with Aravindan Vijayaraghavan)
- Sanchit Kalhan (co-advised with Aravindan Vijayaraghavan)
- Illias Papanikolaou
- Aravind Reddy (co-advised with Aravindan Vijayaraghavan) → Postdoc at the Broad Institute of MIT and Harvard → Visiting Assistant Professor at IIT Hyderabad
- Liren Shan → Research Assistant Professor at Toyota Technological Institute at Chicago
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
- Constraint Satisfaction Problems with Advice
- Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
- SODA 2025 (to appear)
- Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
- Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
- ICML 2024 (oral presentation)
- Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
- Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev
- AAAI 2024 (oral presentation)
- Higher-Order Cheeger Inequality for Partitioning with Buffers
- Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
- SODA 2024
- Random Cuts are Optimal for Explainable k-Medians
- Konstantin Makarychev and Liren Shan
- NeurIPS 2023 (oral presentation)
- Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
- Sayak Chakrabarty and Konstantin Makarychev
- NeurIPS 2023
- Phylogenetic CSPs are Approximation Resistant
- Vaggos Chatziafratis and Konstantin Makarychev
- FOCS 2023
- Approximation Algorithm for Norm Multiway Cut
- Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
- ESA 2023
- Explainable k-means. Don’t be greedy, plant bigger trees!
- Konstantin Makarychev and Liren Shan
- STOC 2022
- 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
Publications
- 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.
- Explainable k-means. Don’t be greedy, plant bigger trees!
- Konstantin Makarychev and Liren Shan
- STOC 2022
- Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
- Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
- STOC 2019
- Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
- Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
- STOC 2018
- 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.
- Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete Graphs
- Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
- STOC 2015
- Constant Factor Approximation for Balanced Cut in the PIE Model
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
- STOC 2014
- Approximation Algorithms for Semi-random Graph Partitioning Problems
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
- STOC 2012
- Integrality Gaps for Sherali-Adams Relaxations
- Moses Charikar, Konstantin Makarychev, Yury Makarychev
- STOC 2009
- Near-Optimal Algorithms for Unique Games
- Moses Charikar, Konstantin Makarychev, Yury Makarychev
- STOC 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
- Phylogenetic CSPs are Approximation Resistant
- Vaggos Chatziafratis and Konstantin Makarychev
- FOCS 2023
- Satisfiability of Ordering CSPs Above Average
- Konstantin Makarychev, Yury Makarychev, Yuan Zhou
- FOCS 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.
- 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.
- Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
- Konstantin Makarychev and Yury Makarychev
- FOCS 2010;
- Israel Journal of Mathematics, vol. 212 (2), May 2016
- 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
- How to Play Unique Games Using Embeddings
- Eden Chlamtac, Konstantin Makarychev, Yury Makarychev
- FOCS 2006
- Constraint Satisfaction Problems with Advice
- Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
- SODA 2025 (to appear)
- Higher-Order Cheeger Inequality for Partitioning with Buffers
- Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
- SODA 2024
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Opršal
- SODA 2017
- 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
- Concentration Inequalities for Nonlinear Matroid Intersection
- Konstantin Makarychev, Warren Schudy, Maxim Sviridenko
- SODA 2012
- Random Structures & Algorithms, vol. 46, no. 3, 2015
- Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms
- Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko
- SODA 2008
- 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
- Directed Metrics and Directed Graph Partitioning Problems
- Moses Charikar, Konstantin Makarychev, Yury Makarychev
- SODA 2006
- 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
- 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
- Maximum Quadratic Assignment Problem
- Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
- ICALP 2010
- ACM Transactions on Algorithms, vol. 10, no. 4, article 18, August 2014
- Random Cuts are Optimal for Explainable k-Medians
- Konstantin Makarychev and Liren Shan
- NeurIPS 2023 (oral presentation)
- Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
- Sayak Chakrabarty and Konstantin Makarychev
- NeurIPS 2023
- Improved Guarantees for k-means++ and k-means++ Parallel
- Konstantin Makarychev, Aravind Reddy, Liren Shan
- NeurIPS 2020
- Correlation Clustering with Local Objectives
- Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou
- NeurIPS 2019
- 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)
- Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
- Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
- ICML 2024 (oral presentation)
- 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
- Correlation Clustering with Asymmetric Classification Errors
- Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
- ICML 2020
- Learning Communities in the Presence of Errors
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
- COLT 2016
- Correlation Clustering with Noisy Partial Information
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
- COLT 2015
- Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
- Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev
- AAAI 2024 (oral presentation)
- 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
- A bi-criteria approximation algorithm for k-Means
- Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
- APPROX 2016
- Approximation Algorithm for Non-Boolean MAX k-CSP
- Konstantin Makarychev and Yury Makarychev
- APPROX 2012
- 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).
- Approximation Algorithm for Norm Multiway Cut
- Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
- ESA 2023
- Speed Regularization and Optimality in Word Classing
- Geoffrey Zweig and Konstantin Makarychev
- ICASSP 2013
- Certified Algorithms: Worst-Case Analysis and Beyond
- Konstantin Makarychev and Yury Makarychev
- ITCS 2020
- Sorting Noisy Data with Partial Information
- Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
- ITCS 2013 – Innovations in Theoretical Computer Science
- Assembly of Circular Genomes
- Konstantin Makarychev and Alantha Newman
- ITCS 2011
- Batch Optimization for DNA Synthesis
- Konstantin Makarychev, Miklos Z. Racz, Cyrus Rashtchian, Sergey Yekhanin
- ISIT 2021
- Indexing Genomic Sequences on the IBM Blue Gene
- Amol Ghoting and Konstantin Makarychev
- SC 2009
- ACM Gordon Bell Prize Finalist
- 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
- 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
- Two-sided Kirszbraun Theorem
- Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev
- SoCG 2021
- Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
- Konstantin Makarychev
- STACS 2013
- On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data
- Howard Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
- STACS 2011
- How to Play Unique Games on Expanders
- Konstantin Makarychev and Yury Makarychev
- WAOA 2010
- 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
- Union of Euclidean Metric Spaces is Euclidean
- Konstantin Makarychev and Yury Makarychev
- Discrete Analysis 2016
- 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
- Quadratic Forms on Graphs and Their Applications
- Konstantin Makarychev
Contact Information
- Department of Computer Science
- Northwestern University
- Mudd Hall, Room 3009
- 2233 Tech Drive, Third Floor
- Evanston, IL 60208
- Email: my_first_name [at] northwestern.edu