| 2026 | STOC | Optimal Phylogenetic Reconstruction from Sampled Quartets. | Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev |
| 2025 | ICML | Sparse-pivot: Dynamic correlation clustering for node insertions. | Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic |
| 2025 | SODA | Constraint Satisfaction Problems with Advice. | Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev |
| 2024 | AAAI | Approximation Scheme for Weighted Metric Clustering via Sherali-Adams. | Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev |
| 2024 | ICML | Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models. | Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic |
| 2024 | SODA | Higher-Order Cheeger Inequality for Partitioning with Buffers. | Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan |
| 2023 | ESA | Approximation Algorithm for Norm Multiway Cut. | Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan |
| 2023 | FOCS | Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. | Vaggos Chatziafratis, Konstantin Makarychev |
| 2022 | STOC | Explainable | Konstantin Makarychev, Liren Shan |
| 2021 | ICML | Local Correlation Clustering with Asymmetric Classification Errors. | Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev |
| 2021 | ICML | Near-Optimal Algorithms for Explainable k-Medians and k-Means. | Konstantin Makarychev, Liren Shan |
| 2021 | ISIT | Batch Optimization for DNA Synthesis. | Konstantin Makarychev, Mikls Z. Rcz, Cyrus Rashtchian, Sergey Yekhanin |
| 2020 | AISTATS | Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. | Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, Mohammad Mahdian |
| 2020 | ICML | Correlation Clustering with Asymmetric Classification Errors. | Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev |
| 2019 | STOC | Performance of Johnson-Lindenstrauss transform for | Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn |
| 2018 | STOC | Nonlinear dimension reduction via outer Bi-Lipschitz extensions. | Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn |
| 2017 | SODA | Robust algorithms with polynomial loss for near-unanimity CSPs. | Vctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal |
| 2017 | STOC | Algorithms for stable and perturbation-resilient problems. | Haris Angelidakis, Konstantin Makarychev, Yury Makarychev |
| 2016 | COLT | Learning Communities in the Presence of Errors. | Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2015 | COLT | Correlation Clustering with Noisy Partial Information. | Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2015 | FOCS | Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. | Konstantin Makarychev, Yury Makarychev, Yuan Zhou |
| 2015 | STOC | Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. | Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev |
| 2015 | SIGCOMM | Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can. | Virajith Jalaparti, Peter Bodk, Ishai Menache, Sriram Rao, Konstantin Makarychev, Matthew Caesar |
| 2014 | FOCS | Solving Optimization Problems with Diseconomies of Scale via Decoupling. | Konstantin Makarychev, Maxim Sviridenko |
| 2014 | ICALP | Nonuniform Graph Partitioning with Unrelated Weights. | Konstantin Makarychev, Yury Makarychev |
| 2014 | ICALP | Precedence-Constrained Scheduling of Malleable Jobs with Preemption. | Konstantin Makarychev, Debmalya Panigrahi |
| 2014 | SODA | Approximation Algorithm for Sparsest | Anand Louis, Konstantin Makarychev |
| 2014 | SODA | Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. | Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2014 | STOC | Constant factor approximation for balanced cut in the PIE model. | Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2013 | ICASSP | Speed regularization and optimality in word classing. | Geoffrey Zweig, Konstantin Makarychev |
| 2013 | STACS | Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs. | Konstantin Makarychev |
| 2012 | SODA | Concentration inequalities for nonlinear matroid intersection. | Konstantin Makarychev, Warren Schudy, Maxim Sviridenko |
| 2012 | STOC | Approximation algorithms for semi-random partitioning problems. | Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2011 | FOCS | Min-max Graph Partitioning and Small Set Expansion. | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
| 2011 | FOCS | The Grothendieck Constant is Strictly Smaller than Krivine's Bound. | Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
| 2011 | FOCS | How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. | Alexandra Kolla, Konstantin Makarychev, Yury Makarychev |
| 2011 | ICALP | Improved Approximation for the Directed Spanner Problem. | Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev |
| 2011 | ICALP | Maximizing Polynomials Subject to Assignment Constraints. | Konstantin Makarychev, Maxim Sviridenko |
| 2011 | STACS | On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. | Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani |
| 2010 | FOCS | Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. | Konstantin Makarychev, Yury Makarychev |
| 2010 | ICALP | Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm. | Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko |
| 2010 | WAOA | How to Play Unique Games on Expanders. | Konstantin Makarychev, Yury Makarychev |
| 2009 | SC | Indexing genomic sequences on the IBM Blue Gene. | Amol Ghoting, Konstantin Makarychev |
| 2009 | SIGMOD | Serial and parallel methods for i/o efficient suffix tree construction. | Amol Ghoting, Konstantin Makarychev |
| 2009 | STOC | Integrality gaps for Sherali-Adams relaxations. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2008 | SODA | Online make-to-order joint replenishment model: primal dual competitive algorithms. | Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko |
| 2007 | FOCS | On the Advantage over Random for Maximum Acyclic Subgraph. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | FOCS | Local Global Tradeoffs in Metric Embeddings. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | SODA | Near-optimal algorithms for maximum constraint satisfaction problems. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | SODA | A divide and conquer algorithm for | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2006 | FOCS | How to Play Unique Games Using Embeddings. | Eden Chlamtac, Konstantin Makarychev, Yury Makarychev |
| 2006 | SODA | Directed metrics and directed graph partitioning problems. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2006 | STOC | Near-optimal algorithms for unique games. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2005 | STOC | O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. | Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2005 | STOC | Quadratic forms on graphs. | Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor |