Faculty DirectoryKonstantin Makarychev

Professor of Computer Science
Associate Chair for Graduate Studies
Contact
2233 Tech DriveMudd Room 3009
Evanston, IL 60208-3109
Email Konstantin Makarychev
Website
Konstantin Makarychev's Homepage
Departments
Education
Ph.D. Computer Science, Princeton University, Princeton, NJ
B.S. Mechanics and Mathematics, Moscow State University, Moskva, Russia
Biography
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 to computer science.
Before joining Northwestern University, I was a researcher at Microsoft and IBM Research Labs. I obtained my PhD in Computer Science from Princeton University in 2007.
Research Interests
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.
Selected Publications
Constraint Satisfaction Problems with Advice
Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
SODA 2025 (to appear)
Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
ICML 2024 (oral presentation)
Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev
AAAI 2024 (oral presentation)
Higher-Order Cheeger Inequality for Partitioning with Buffers
Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
SODA 2024
Random Cuts are Optimal for Explainable k-Medians
Konstantin Makarychev and Liren Shan
NeurIPS 2023 (oral presentation)
Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
Sayak Chakrabarty and Konstantin Makarychev
NeurIPS 2023
Phylogenetic CSPs are Approximation Resistant
Vaggos Chatziafratis and Konstantin Makarychev
FOCS 2023
Approximation Algorithm for Norm Multiway Cut
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
ESA 2023
Explainable k-means. Don’t be greedy, plant bigger trees!
Konstantin Makarychev and Liren Shan
STOC 2022
Near-optimal algorithms for explainable k-medians and k-means
Konstantin Makarychev and Liren Shan
ICML 2021
Local Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
ICML 2021
Batch Optimization for DNA Synthesis
Konstantin Makarychev, Miklos Z. Racz, Cyrus Rashtchian, Sergey Yekhanin
ISIT 2021
Two-sided Kirszbraun Theorem
Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev
SoCG 2021
Improved Guarantees for k-means++ and k-means++ Parallel
Konstantin Makarychev, Aravind Reddy, Liren Shan
NeurIPS 2020
Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
ICML 2020
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev
AISTATS 2020