Faculty Directory
Konstantin Makarychev

Professor of Computer Science

Associate Chair for Graduate Studies

Contact

2233 Tech Drive
Mudd Room 3009
Evanston, IL 60208-3109

Email Konstantin Makarychev

Website

Konstantin Makarychev's Homepage


Departments

Computer Science



Download CV

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