Konstantin Makarychev's Photo

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

Recent and Upcoming Talks

  • IDEAL Get Ready for Research Workshop at University of Illinois Chicago, November 8, 2025: Explainable k-means and k-medians Clustering
  • Workshop on Constraint Satisfaction Problems at Dagstuhl, May 19, 2025: Phylogenetic CSPs are Approximation Resistant
  • Workshop on Clustering at EnCORE, UCSD, March 4, 2024: Correlation Clustering Algorithm for Streaming, Dynamic, Parallel, and Local Computation Models

Teaching

Northwestern University

  • Design and Analysis of Algorithms: Winter 2026, Winter 2024, Fall 2022, Fall 2021, Winter 2021, Winter 2020, Winter 2019, Spring 2018, Winter 2018
  • Graduate Algorithms (syllabus): Spring 2026, Fall 2024, Spring 2024, Fall 2020, Spring 2020
  • Approximation Algorithms (syllabus): Fall 2025, 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

Surveys and Book Chapters

  1. Perturbation Resilience
    • Konstantin Makarychev and Yury Makarychev
    • Beyond the Worst-Case Analysis of Algorithms. Editor: Tim Roughgarden. Cambridge University Press. 2020.
  2. 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.
  3. 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

  1. Near-optimal Explainable k-means Clustering under Lp Norm
  2. On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
  3. Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP
  4. Strong Refutation of Ordering, Phylogenetic, and Ordinary CSPs, and New Satisfiability and Refutation Thresholds for Triplet and Quartet Reconstruction
  5. Optimal Phylogenetic Reconstruction from Sampled Quartets
  6. Simple Average-case Analysis of Recursive Randomized Greedy MIS
  7. Dynamic Algorithm for Explainable k-medians Clustering under ℓp Norm
  8. Sparse-pivot: Dynamic correlation clustering for node insertions
  9. Constraint Satisfaction Problems with Advice
  10. Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
  11. Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
  12. Higher-Order Cheeger Inequality for Partitioning with Buffers
  13. Random Cuts are Optimal for Explainable k-Medians
    • Konstantin Makarychev and Liren Shan
    • NeurIPS 2023 (oral presentation)
  14. Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
    • Sayak Chakrabarty and Konstantin Makarychev
    • NeurIPS 2023
  15. Phylogenetic CSPs are Approximation Resistant
  16. Approximation Algorithm for Norm Multiway Cut
  17. Explainable k-means. Don’t be greedy, plant bigger trees!
  18. Near-optimal algorithms for explainable k-medians and k-means
  19. Local Correlation Clustering with Asymmetric Classification Errors
  20. Batch Optimization for DNA Synthesis
  21. Two-sided Kirszbraun Theorem
  22. Improved Guarantees for k-means++ and k-means++ Parallel
  23. Correlation Clustering with Asymmetric Classification Errors
  24. Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
  25. Certified Algorithms: Worst-Case Analysis and Beyond
  26. Correlation Clustering with Local Objectives
  27. Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
  28. DNA assembly for nanopore data storage readout
  29. Scaling up DNA data storage and random access retrieval
  30. Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
  31. Clustering Billions of Reads for DNA Data Storage
  32. Algorithms for Stable and Perturbation-Resilient Problems
  33. Robust algorithms with polynomial loss for near-unanimity CSPs
  34. Learning Communities in the Presence of Errors
  35. Union of Euclidean Metric Spaces is Euclidean
  36. A bi-criteria approximation algorithm for k-Means
  37. Satisfiability of Ordering CSPs Above Average
  38. Correlation Clustering with Noisy Partial Information
  39. Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete Graphs
  40. Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can
  41. Solving Optimization Problems with Diseconomies of Scale
  42. Nonuniform Graph Partitioning with Unrelated Weights
  43. Precedence-constrained Scheduling of Malleable Jobs with Preemption
  44. Constant Factor Approximation for Balanced Cut in the PIE Model
  45. Bilu-Linial Stable Instances of Max Cut
  46. Approximation Algorithm for Sparsest k-Partitioning
  47. Speed Regularization and Optimality in Word Classing
  48. Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
    • Konstantin Makarychev
    • STACS 2013
  49. Sorting Noisy Data with Partial Information
  50. Approximation Algorithm for Non-Boolean MAX k-CSP
  51. Approximation Algorithms for Semi-random Graph Partitioning Problems
  52. Concentration Inequalities for Nonlinear Matroid Intersection
  53. The Grothendieck Constant is Strictly Smaller than Krivine's Bound
  54. How to Play Unique Games Against a Semi-random Adversary
  55. Min-Max Graph Partitioning and Small Set Expansion
  56. Improved Approximation for the Directed Spanner Problem
  57. Maximizing Polynomials Subject to Assignment Constraints
  58. On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data
  59. Assembly of Circular Genomes
  60. Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
  61. Maximum Quadratic Assignment Problem
  62. How to Play Unique Games on Expanders
  63. On Hardness of Pricing Items for Single-Minded Bidders
  64. Integrality Gaps for Sherali-Adams Relaxations
  65. Indexing Genomic Sequences on the IBM Blue Gene
    • Amol Ghoting and Konstantin Makarychev
    • SC 2009
    • ACM Gordon Bell Prize Finalist
  66. 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
  67. Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms
  68. Local Global Tradeoffs in Metric Embeddings
  69. On the Advantage over Random for Maximum Acyclic Subgraph
  70. Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems
  71. A Divide and Conquer Algorithm for d-Dimensional Linear Arrangement
  72. How to Play Unique Games Using Embeddings
  73. Near-Optimal Algorithms for Unique Games
  74. Directed Metrics and Directed Graph Partitioning Problems
  75. Square root log n approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems
  76. Quadratic Forms on Graphs
  77. Chain Independence and Common Information
    • Konstantin Makarychev and Yury Makarychev
    • IEEE Transactions on Information Theory, 58(8), pp. 5279-5286, 2012
  78. A new class of non Shannon type inequalities for entropies
  79. The Importance of Being Formal
    • Konstantin Makarychev and Yury Makarychev
    • The Mathematical Intelligencer, vol. 23 no. 1, 2001
  80. Proof of Pak's conjecture on tilings by T-tetrominoes (in Russian)

PhD Thesis

  1. Quadratic Forms on Graphs and Their Applications
    • Konstantin Makarychev

Publications

Surveys (3)
STOC (12)
FOCS (10)
SODA (10)
ICALP (5)
NeurIPS (7)
ICML (5)
COLT (2)
AAAI (1)
AISTATS (1)
APPROX (4)
ESA (1)
ICASSP (1)
ITCS (3)
ISIT (1)
SC (1)
SIGCOMM (1)
SIGMOD (1)
SoCG (1)
SOSA (1)
STACS (2)
WAOA (1)
Journals* (6)
*This section excludes journal papers previously published in conference proceedings.
Manuscripts (3)
PhD Thesis (1)

Contact Information

  • Department of Computer Science
  • Northwestern University
  • Mudd Hall, Room 3009
  • 2233 Tech Drive, Third Floor
  • Evanston, IL 60208
  • Email: click to show