Konstantin Makarychev

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

Employment

09/2021 – present
  • Northwestern University, Evanston, IL
  • Professor of Computer Science
01/2023 – 08/2025
  • Northwestern University, Evanston, IL
  • Associate Chair for Graduate Studies (DGS) at the Computer Science Department
02/2017 – 08/2023
  • Microsoft Research, Redmond, WA
  • Consultant
02/2017 – 09/2021
  • Northwestern University, Evanston, IL
  • Associate Professor of Computer Science (with tenure)
04/2012 – 01/2017
  • Microsoft Research, Redmond, WA
  • Researcher, Theory Group
07/2007 – 04/2012
  • IBM Research, Yorktown Heights, NY
  • Research Staff Member, Algorithms Group
06/2006 – 09/2006
  • IBM Research, Yorktown Heights, NY
  • Intern, Algorithms Group
  • Mentor: Maxim Sviridenko
06/2005 – 09/2005
  • Microsoft Research, Redmond, WA
  • Intern, Theory Group
  • Mentor: Assaf Naor
01/2002 – 08/2003
  • Siebel Systems, San Mateo, CA
  • Software Engineer, Core Engineering

Education

2003 – 2007
  • Department of Computer Science, Princeton University
  • Ph.D. in Computer Science
  • Advisor: Moses Charikar
1996 – 2001
  • Department of Mathematics, Moscow University
  • M.S. in Pure and Applied Mathematics
  • Diploma with Honors; GPA 5.0/5.0
  • Advisors: Alexander Shen and Nikolai Vereshchagin
1992 – 1996
  • Moscow Math High School #57

Current and Former PhD Students

Postdocs

Summer Interns

Microsoft Research

IBM Research

Undergraduate Research Advisees

Professional Service

  • Program Committee Member: STOC 2025, STOC 2022, ICALP 2021, SODA 2020, ESA 2018, STOC 2016, APPROX 2014, CSR 2014, ICALP 2013, CSR 2013, SODA 2013, APPROX 2012, STOC 2008
  • General co-chair for STOC 2020
  • PhD Dissertation Committees: Abhratanu Dutta (Northwestern University), Emirhan Gürpinar (Montpellier University), Jafar Jafarov (Toyota Technological Institute at Chicago), Tarik Kaced (Montpellier University), Aravindan Vijayaraghavan (Princeton University)
  • Grant reviewing for the National Science Foundation (NSF) and Israel Science Foundation (ISF)
  • Refereeing for APPROX, COLT, CSR, ESA, FOCS, ICALP, ICML, PODC, SODA, STACS, STOC, WINE (conferences); and Algorithmica, Combinatorica, Discrete Optimization, Information Processing Letters, Journal of ACM, Journal of Global Optimization, Mathematics of Operations Research, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Theoretical Computer Science (journals)

Research Funding

2020 – 2025
NSF Award CCF-1955351 for Collaborative Medium Research Project “Design and Analysis of Models and Algorithms for Real-life Problems.” This is a joint project with Yury Makarychev.
2019 – 2022
Team member of the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL). The institute is supported by NSF Award CCF-1934931.

Awards and Honors

2011
IBM A-Level Accomplishment for work on Semidefinite Programming
2010
IBM Research 2009 Pat Goldberg Memorial Best Paper Award
2006 – 2007
IBM Ph.D. Fellowship
2003 – 2007
Gordon Wu Fellowship
2003
Siebel Engineering Outstanding Contributor Award
1996 – 1997
George Soros Fellowship
1996
Russian Mathematical Olympiad – Silver Medal

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

Summer Schools

  • Metric Geometry and Its Applications in Computer Science (CS Club, Saint Petersburg, Russia): Fall 2017
  • Approximation Algorithms (CSR Conference): Summer 2013

Teaching Assistant at Princeton University

Math Instructor

  • Math circle classes for high school students at Moscow High School #57, Moscow University, and Moscow Center for Continuous Mathematical Education: 1996 – 1998, 2000 – 2001

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

PhD Thesis

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

Patents

  1. Serial and parallel methods for I/O efficient suffix tree construction.
  2. Efficient clustering of noisy polynucleotide sequence reads.
  3. Efficient payload extraction from polynucleotide sequence reads.
  4. Efficient polymer synthesis.