A short proof of Kuratowski's graph planarity criterion. - Yury Makarychev (J. Graph Theory, 1997)

A new class of non-Shannon-type inequalities for entropies. - Konstantin Makarychev; Yury Makarychev; Andrei E. Romashchenko; Nikolai K. Vereshchagin (Commun. Inf. Syst., 2002)

O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. - Amit Agarwal; Moses Charikar; Konstantin Makarychev; Yury Makarychev (STOC, 2005)

Quadratic forms on graphs. - Noga Alon; Konstantin Makarychev; Yury Makarychev; Assaf Naor (STOC, 2005)

Conditionally independent random variables - Konstantin Makarychev; Yury Makarychev (CoRR, 2005)

How to Play Unique Games Using Embeddings. - Eden Chlamtac; Konstantin Makarychev; Yury Makarychev (FOCS, 2006)

Directed metrics and directed graph partitioning problems. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (SODA, 2006)

Near-optimal algorithms for unique games. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (STOC, 2006)

Approximation Algorithm for the Max k-CSP Problem. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2006)

Note on MAX 2SAT. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2006)

A divide and conquer algorithm for d-dimensional arrangement. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (SODA, 2007)

On the Advantage over Random for Maximum Acyclic Subgraph. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2007)

Integrality gaps for Sherali-Adams relaxations. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (STOC, 2009)

Balanced Allocation: Memory Performance Tradeoffs - Itai Benjamini; Yury Makarychev (CoRR, 2009)

How to Play Unique Games on Expanders. - Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2009)

Near-optimal algorithms for maximum constraint satisfaction problems. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (ACM Trans. Algorithms, 2009)

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. - Konstantin Makarychev; Yury Makarychev (FOCS, 2010)

Subgraph sparsification and nearly optimal ultrasparsifiers. - Alexandra Kolla; Yury Makarychev; Amin Saberi; Shang-Hua Teng (STOC, 2010)

Local Global Tradeoffs in Metric Embeddings. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (SIAM J. Comput., 2010)

The Grothendieck Constant is Strictly Smaller than Krivine's Bound. - Mark Braverman; Konstantin Makarychev; Yury Makarychev; Assaf Naor (FOCS, 2011)

How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. - Alexandra Kolla; Konstantin Makarychev; Yury Makarychev (FOCS, 2011)

Finding Almost-Perfect Graph Bisections. - Venkatesan Guruswami; Yury Makarychev; Prasad Raghavendra; David Steurer; Yuan Zhou 007 (ICS, 2011)

On Graph Crossing Number and Edge Planarization. - Julia Chuzhoy; Yury Makarychev; Anastasios Sidiropoulos (SODA, 2011)

How to Play Unique Games against a Semi-Random Adversary - Alexandra Kolla; Konstantin Makarychev; Yury Makarychev (CoRR, 2011)

Approximation Algorithms and Hardness of the k-Route Cut Problem - Julia Chuzhoy; Yury Makarychev; Aravindan Vijayaraghavan; Yuan Zhou 007 (CoRR, 2011)

Approximation Algorithm for Non-boolean MAX k-CSP. - Konstantin Makarychev; Yury Makarychev (APPROX-RANDOM, 2012)

Planarizing an Unknown Surface. - Yury Makarychev; Anastasios Sidiropoulos (APPROX-RANDOM, 2012)

Approximation algorithms for semi-random partitioning problems. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (STOC, 2012)

Approximation Algorithms for Semi-random Graph Partitioning Problems - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2012)

Simple linear time approximation algorithm for betweenness. - Yury Makarychev (Oper. Res. Lett., 2012)

Chain Independence and Common Information. - Konstantin Makarychev; Yury Makarychev (IEEE Trans. Inf. Theory, 2012)

Sorting noisy data with partial information. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (ITCS, 2013)

The Power of Asymmetry in Binary Hashing. - Behnam Neyshabur; Nati Srebro; Ruslan Salakhutdinov; Yury Makarychev; Payman Yadollahpour (NIPS, 2013)

Bilu-Linial Stable Instances of Max Cut - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2013)

Clustering, Hamming Embedding, Generalized LSH and the Max Norm. - Behnam Neyshabur; Yury Makarychev; Nathan Srebro (ALT, 2014)

Nonuniform Graph Partitioning with Unrelated Weights. - Konstantin Makarychev; Yury Makarychev (ICALP (1), 2014)

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (SODA, 2014)

Constant factor approximation for balanced cut in the PIE model. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (STOC, 2014)

Algorithms for Semi-random Correlation Clustering. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2014)

Approximation Algorithm for Non-Boolean Max-k-CSP. - Konstantin Makarychev; Yury Makarychev (Theory Comput., 2014)

Correlation Clustering with Noisy Partial Information. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (COLT, 2015)

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. - Konstantin Makarychev; Yury Makarychev; Yuan Zhou 007 (FOCS, 2015)

Satisfiability of Ordering CSPs Above Average. - Konstantin Makarychev; Yury Makarychev; Yuan Zhou 007 (CoRR, 2015)

A Bi-Criteria Approximation Algorithm for k-Means. - Konstantin Makarychev; Yury Makarychev; Maxim Sviridenko; Justin Ward (APPROX-RANDOM, 2016)

Learning Communities in the Presence of Errors. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (COLT, 2016)

Metric Perturbation Resilience. - Konstantin Makarychev; Yury Makarychev (CoRR, 2016)

Approximation Algorithms and Hardness of the k-Route Cut Problem. - Julia Chuzhoy; Yury Makarychev; Aravindan Vijayaraghavan; Yuan Zhou 007 (ACM Trans. Algorithms, 2016)

Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion. - Anand Louis; Yury Makarychev (Theory Comput., 2016)

Approximation Algorithms for CSPs. - Konstantin Makarychev; Yury Makarychev (The Constraint Satisfaction Problem, 2017)

An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut. - Haris Angelidakis; Yury Makarychev; Pasin Manurangsi (IPCO, 2017)

Algorithmic and Hardness Results for the Hub Labeling Problem. - Haris Angelidakis; Yury Makarychev; Vsevolod Oparin (SODA, 2017)

Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. - Eden Chlamtác; Michael Dinitz; Yury Makarychev (SODA, 2017)

Algorithms for stable and perturbation-resilient problems. - Haris Angelidakis; Konstantin Makarychev; Yury Makarychev (STOC, 2017)

A Pseudo-Approximation for the Genus of Hamiltonian Graphs. - Yury Makarychev; Amir Nayyeri; Anastasios Sidiropoulos (Theory Comput., 2017)

Nonlinear dimension reduction via outer Bi-Lipschitz extensions. - Sepideh Mahabadi; Konstantin Makarychev; Yury Makarychev; Ilya P. Razenshteyn (STOC, 2018)

Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering. - Konstantin Makarychev; Yury Makarychev; Ilya P. Razenshteyn (STOC, 2019)

Regression via Kirszbraun Extension with Applications to Imitation Learning. - Armin Biess; Aryeh Kontorovich; Yury Makarychev; Hanan Zaichyk (CoRR, 2019)

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. - Víctor Dalmau; Marcin Kozik; Andrei A. Krokhin; Konstantin Makarychev; Yury Makarychev; Jakub Oprsal (SIAM J. Comput., 2019)

Performance of Johnson-Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering. - Konstantin Makarychev; Yury Makarychev; Ilya P. Razenshteyn (SIAM J. Comput., 2019)

Perturbation Resilience. - Konstantin Makarychev; Yury Makarychev (Beyond the Worst-Case Analysis of Algorithms, 2020)

Correlation Clustering with Asymmetric Classification Errors. - Jafar Jafarov; Sanchit Kalhan; Konstantin Makarychev; Yury Makarychev (ICML, 2020)

Certified Algorithms: Worst-Case Analysis and Beyond. - Konstantin Makarychev; Yury Makarychev (ITCS, 2020)

Approximation Algorithms for Socially Fair Clustering. - Yury Makarychev; Ali Vakilian (COLT, 2021)

Two-Sided Kirszbraun Theorem. - Arturs Backurs; Sepideh Mahabadi; Konstantin Makarychev; Yury Makarychev (SoCG, 2021)

Local Correlation Clustering with Asymmetric Classification Errors. - Jafar Jafarov; Sanchit Kalhan; Konstantin Makarychev; Yury Makarychev (ICML, 2021)

Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. - Yury Makarychev; Naren Sarayu Manoj; Max Ovsiankin (COLT, 2022)

Fair Representation Clustering with Several Protected Classes. - Zhen Dai; Yury Makarychev; Ali Vakilian (FAccT, 2022)

Approximating Fair Clustering with Cascaded Norm Objectives. - Eden Chlamtác; Yury Makarychev; Ali Vakilian (SODA, 2022)

Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment. - Eden Chlamtác; Yury Makarychev; Ali Vakilian (APPROX/RANDOM, 2023)

Approximation Algorithm for Norm Multiway Cut. - Charlie Carlson; Jafar Jafarov; Konstantin Makarychev; Yury Makarychev; Liren Shan (ESA, 2023)

Approximating Red-Blue Set Cover. - Eden Chlamtác; Yury Makarychev; Ali Vakilian (CoRR, 2023)

Approximation Algorithms for Norm Multiway Cut. - Charlie Carlson; Jafar Jafarov; Konstantin Makarychev; Yury Makarychev; Liren Shan (CoRR, 2023)

Approximation Algorithms for 𝓁p-Shortest Path and 𝓁p-Group Steiner Tree. - Yury Makarychev; Max Ovsiankin; Erasmo Tani (ICALP, 2024)

Higher-Order Cheeger Inequality for Partitioning with Buffers. - Konstantin Makarychev; Yury Makarychev; Liren Shan; Aravindan Vijayaraghavan (SODA, 2024)

Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. - Yury Makarychev; Naren Sarayu Manoj; Max Ovsiankin (STOC, 2024)

A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering. - Sayan Bandyapadhyay; Eden Chlamtác; Yury Makarychev; Ali Vakilian (CoRR, 2024)

Efficient Kirszbraun extension with applications to regression. - Hananel Zaichyk; Armin Biess; Aryeh Kontorovich; Yury Makarychev (Math. Program., 2024)

Correction: Efficient Kirszbraun extension with applications to regression. - Hananel Zaichyk; Armin Biess; Aryeh Kontorovich; Yury Makarychev (Math. Program., 2024)

Max-Cut with Multiple Cardinality Constraints. - Yury Makarychev; Madhusudhan Reddy Pittu; Ali Vakilian (APPROX/RANDOM, 2025)

Constraint Satisfaction Problems with Advice. - Suprovat Ghoshal; Konstantin Makarychev; Yury Makarychev (SODA, 2025)