Konstantin Makarychev's Photo


 

About me

I am an Associate 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 a tentative syllabus for my Graduate Algorithms course here: Fall 2020 Syllabus. This quarter, I also post lectures on algorithms in Russian. You can find my video notes here.

PhD Program and Postdoc Positions in Theoretical CS

  • If you are interested in algorithms and theoretical computer science, we encourage you to apply to the PhD program at Northwestern University (more info).
  • We are looking for postdocs in approximation algorithms, beyond-worst-case analysis of algorithms, and/or high-dimensional data analysis (more info).

Talks

  • Yahoo Research, 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

Events at Northwestern

Teaching

Northwestern University

  • Design and Analysis of Algorithms: Fall 2021, Winter 2021, Winter 2020, Winter 2019, Spring 2018, and Winter 2018
  • Advanced Algorithm Design Through the Lens of Competitive Programming: Winter 2022
  • Algorithms for Big Data: Spring 2022
  • Approximation Algorithms: Winter 2021, Spring 2019, and Spring 2017
  • Graduate Algorithms: Fall 2020, Spring 2020
  • Math Toolkit for Theoretical Computer Scientists: Spring 2019
  • Advanced Topics in Approximation Algorithms: Spring 2020

University of Washington

  • Linear and Semi-Definite Programming in Approximation Algorithms (with Mohit Singh): Fall 2014

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

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