Konstantin Makarychev

  • 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

Employment

02/2017 – present
  • Northwestern University, Evanston, IL
  • Associate Professor of Computer Science (with tenure)
01/2017 – present
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

Teaching

Northwestern University

  • Design and Analysis of Algorithms: Winter 2020, Winter 2019, Spring 2018, and Winter 2018
  • Graduate Algorithms: Spring 2020
  • Advanced Topics in Approximation Algorithms: Spring 2020
  • Approximation Algorithms: Spring 2019 and Spring 2017
  • Math Toolkit for Theoretical Computer Scientists: Spring 2019

University of Washington

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

PhD Students

Professional Service

  • Editorial Board Member: SICOMP
  • Program Committee Member: STOC 2008, APPROX 2012, SODA 2013, CSR 2013, ICALP 2013, CSR 2014, APPROX 2014, STOC 2016, ESA 2018, SODA 2020
  • Refereeing for APPROX, COLT, CSR, ESA, FOCS, ICALP, ICML, SODA, STACS, STOC, PODC, 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)
  • Grant reviewing for National Science Foundation (NSF)

Research Funding

2020 – 2024
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

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.

Publications

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

PhD Thesis

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