| 2026 | SODA | Hardness of Approximation for Shortest Path with Vector Costs. | Charlie Carlson, Yury Makarychev, Ron Mosenzon |
| 2026 | STOC | Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs. | Yury Makarychev |
| 2025 | SODA | Constraint Satisfaction Problems with Advice. | Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev |
| 2024 | ICALP | Approximation Algorithms for 𝓁 | Yury Makarychev, Max Ovsiankin, Erasmo Tani |
| 2024 | SODA | Higher-Order Cheeger Inequality for Partitioning with Buffers. | Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan |
| 2024 | STOC | Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. | Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin |
| 2023 | ESA | Approximation Algorithm for Norm Multiway Cut. | Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan |
| 2022 | COLT | Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. | Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin |
| 2022 | SODA | Approximating Fair Clustering with Cascaded Norm Objectives. | Eden Chlamtc, Yury Makarychev, Ali Vakilian |
| 2021 | COLT | Approximation Algorithms for Socially Fair Clustering. | Yury Makarychev, Ali Vakilian |
| 2021 | ICML | Local Correlation Clustering with Asymmetric Classification Errors. | Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev |
| 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 | IPCO | An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut. | Haris Angelidakis, Yury Makarychev, Pasin Manurangsi |
| 2017 | SODA | Algorithmic and Hardness Results for the Hub Labeling Problem. | Haris Angelidakis, Yury Makarychev, Vsevolod Oparin |
| 2017 | SODA | Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. | Eden Chlamtc, Michael Dinitz, Yury Makarychev |
| 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 |
| 2014 | ALT | Clustering, Hamming Embedding, Generalized LSH and the Max Norm. | Behnam Neyshabur, Yury Makarychev, Nathan Srebro |
| 2014 | ICALP | Nonuniform Graph Partitioning with Unrelated Weights. | Konstantin Makarychev, Yury 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 |
| 2012 | SODA | Approximation algorithms and hardness of the | Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou |
| 2012 | STOC | Approximation algorithms for semi-random partitioning problems. | Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 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 | SODA | On Graph Crossing Number and Edge Planarization. | Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos |
| 2010 | FOCS | Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. | Konstantin Makarychev, Yury Makarychev |
| 2010 | STOC | Subgraph sparsification and nearly optimal ultrasparsifiers. | Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng |
| 2010 | WAOA | How to Play Unique Games on Expanders. | Konstantin Makarychev, Yury Makarychev |
| 2009 | STOC | Integrality gaps for Sherali-Adams relaxations. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 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 |