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, 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.

Talks

  • TTIC Workshop on Recent Trends in Clustering, September 18, 2019: Correlation Clustering
  • UPenn, October 25, 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
  • Illinois Institute of Technology, November 19, 2019: Dimensionality Reduction for k-Means and k-Medians Clustering
  • Technion, December 2, 2019: Dimensionality Reduction for k-Means and k-Medians Clustering

Workshops

Teaching

Northwestern University

  • Design and Analysis of Algorithms: Winter 2020, Winter 2019, Spring 2018, and Winter 2018
  • Graduate Algorithms: Spring 2020
  • Approximation Algorithms: Spring 2019 and Spring 2017
  • 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

PhD Students

Surveys

  1. Approximation Algorithms for CSPs (a survey of results),
    • Konstantin Makarychev and Yury Makarychev
    • The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Zivny (Eds.), Dagstuhl Follow-Ups.
    •  
  2. 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 (Eds.). MIT Press, 2016.
    • You can download a draft copy of the survey here.
    •  

Publications — Theory

  1. Correlation Clustering with Local Objectives,
    • Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou
    • NeurIPS 2019, to appear
    •  
  2. Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering,
  3. Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions,
  4. Algorithms for Stable and Perturbation-Resilient Problems,
  5. Robust algorithms with polynomial loss for near-unanimity CSPs,
  6. Learning Communities in the Presence of Errors,
  7. Union of Euclidean Metric Spaces is Euclidean,
  8. A bi-criteria approximation algorithm for k-Means,
  9. Satisfiability of Ordering CSPs Above Average,
  10. Correlation Clustering with Noisy Partial Information,
  11. Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete Graphs,
  12. Solving Optimization Problems with Diseconomies of Scale,
  13. Nonuniform Graph Partitioning with Unrelated Weights,
  14. Precedence-constrained Scheduling of Malleable Jobs with Preemption,
  15. Constant Factor Approximation for Balanced Cut in the PIE Model,
  16. Bilu-Linial Stable Instances of Max Cut,
  17. Approximation Algorithm for Sparsest k-Partitioning,
  18. Local Search is Better than Random Assignment for
    Bounded Occurrence Ordering k-CSPs,
    • Konstantin Makarychev
    • STACS 2013
    •  
  19. Sorting Noisy Data with Partial Information,
  20. Approximation Algorithm for Non-Boolean MAX k-CSP,
  21. Approximation Algorithms for Semi-random Graph Partitioning Problems,
  22. Concentration Inequalities for Nonlinear Matroid Intersection,
  23. The Grothendieck Constant is Strictly Smaller than Krivine's Bound,
  24. How to Play Unique Games Against a Semi-random Adversary,
  25. Min-Max Graph Partitioning and Small Set Expansion,
  26. Improved Approximation for the Directed Spanner Problem,
  27. Maximizing Polynomials Subject to Assignment Constraints,
  28. On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data,
  29. Assembly of Circular Genomes,
  30. Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability,
  31. Maximum Quadratic Assignment Problem,
  32. How to Play Unique Games on Expanders,
  33. On Hardness of Pricing Items for Single-Minded Bidders,
  34. Integrality Gaps for Sherali-Adams Relaxations,
  35. Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms,
  36. Local Global Tradeoffs in Metric Embeddings,
  37. On the Advantage over Random for Maximum Acyclic Subgraph,
  38. Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems,
  39. A Divide and Conquer Algorithm for d-Dimensional Linear Arrangement,
  40. How to Play Unique Games Using Embeddings,
  41. Near-Optimal Algorithms for Unique Games,
  42. Directed Metrics and Directed Graph Partitioning Problems,
  43. Square root log n approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems,
  44. Quadratic Forms on Graphs,
  45. Chain Independence and Common Information,
  46. A new class of non Shannon type inequalities for entropies,
  47. The Importance of Being Forma
  48. Proof of Pak's conjecture on tilings by T-tetrominoes (in Russian),

Publications — Applied CS

  1. DNA assembly for nanopore data storage readout
  2. Scaling up DNA data storage and random access retrieval
  3. Clustering Billions of Reads for DNA Data Storage
  4. Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can
  5. Speed Regularization and Optimality in Word Classing
  6. Indexing Genomic Sequences on the IBM Blue Gene,
    • Amol Ghoting and Konstantin Makarychev
    • SC 2009
    • ACM Gordon Bell Prize Finalist
    •  
  7. Serial and Parallel Methods for I/O Efficient Suffix Tree Construction,
    • Amol Ghoting and Konstantin Makarychev
    • SIGMOD 2009, pp. 827-840
    • ACM Transactions on Database Systems (TODS), vol. 35(4), pp. 25:1-25:37
    • IBM Pat Goldberg Best Paper Award
    •  

PhD Thesis

  1.  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