YM
Yury Makarychev
cs.DScs.LGcs.CGmath.MGcs.CCstat.MLcs.AIcs.CLcs.CVcs.DM
On Valency
published · living versionsW_qrnha7w5·v1 · currentpublished
A bi-criteria approximation algorithm for Means
with Konstantin Makarychev, Maxim Sviridenko, Justin Ward
1 version
Preprints & journals
50 papers in the corpus · 2007–2026Socially Fair Clustering: Parameterized Approximation and Local Search2608.30026v1 · Aditya Anand, Yury Makarychev, Liren Shan2026 · 0 citationsarXiv
Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP2608.07800v1 · Yury Makarychev2026 · 0 citationsarXiv
Humanity's Last Exam2501.14249v11 · Long Phan, Alice Gatti, Ziwen Han et al.2025 · 23 citationsarXiv
Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP2607.11050v1 · Suprovat Ghoshal, Neng Huang, Euiwoong Lee et al.2026 · 0 citationsarXiv
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets2604.10318v1 · Suprovat Ghoshal, Neng Huang, Euiwoong Lee et al.2026 · 0 citationsarXiv
Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs2603.30020v1 · Yury Makarychev2026 · 0 citationsarXiv
Hardness of Approximation for Shortest Path with Vector Costs2510.21058v1 · Charlie Carlson, Yury Makarychev, Ron Mosenzon2025 · 0 citationsarXiv
Max-Cut with Multiple Cardinality Constraints2507.12607v1 · Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian2025 · 0 citationsarXiv
Constraint Satisfaction Problems with Advice2403.02212v2 · Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev2024 · 0 citationsarXiv
Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree2404.17669v1 · Yury Makarychev, Max Ovsiankin, Erasmo Tani2024 · 0 citationsarXiv
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes2311.09460v1 · Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin2023 · 1 citationarXiv
Higher-Order Cheeger Inequality for Partitioning with Buffers2308.10160v1 · Konstantin Makarychev, Yury Makarychev, Liren Shan et al.2023 · 0 citationsarXiv
Approximation Algorithms for Norm Multiway Cut2308.08373v1 · Charlie Carlson, Jafar Jafarov, Konstantin Makarychev et al.2023 · 0 citationsarXiv
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment2302.00213v2 · Eden Chlamt'ac, Yury Makarychev, Ali Vakilian2023 · 0 citationsarXiv
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes2206.07250v1 · Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin2022 · 2 citationsarXiv
Efficient Kirszbraun Extension with Applications to Regression1905.11930v3 · Hanan Zaichyk, Armin Biess, Aryeh Kontorovich et al.2019 · 0 citationsarXiv
Fair Representation Clustering with Several Protected Classes2202.01391v1 · Zhen Dai, Yury Makarychev, Ali Vakilian2022 · 2 citationsarXiv
Approximating Fair Clustering with Cascaded Norm Objectives2111.04804v1 · Eden Chlamt'ac, Yury Makarychev, Ali Vakilian2021 · 15 citationsarXiv
Correlation Clustering with Asymmetric Classification Errors2108.05696v1 · Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev et al.2021 · 2 citationsarXiv
Local Correlation Clustering with Asymmetric Classification Errors2108.05697v1 · Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev et al.2021 · 3 citationsarXiv
Approximation Algorithms for Socially Fair Clustering2103.02512v2 · Yury Makarychev, Ali Vakilian2021 · 8 citationsarXiv
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering1811.03195v2 · Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn2018 · 74 citationsarXiv
Robust algorithms with polynomial loss for near-unanimity CSPs1607.04787v4 · V'ictor Dalmau, Marcin Kozik, Andrei Krokhin et al.2016 · 7 citationsarXiv
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions1811.03591v1 · Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev et al.2018 · 27 citationsarXiv
A Union of Euclidean Metric Spaces is Euclidean1602.08426v3 · Konstantin Makarychev, Yury Makarychev2016 · 8 citationsA Union of Euclidean Metric Spaces is Euclidean, Discrete Analysis 2016:14
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion1611.07866v1 · Eden Chlamt'ac, Michael Dinitz, Yury Makarychev2016 · 30 citationsarXiv
Algorithmic and Hardness Results for the Hub Labeling Problem1611.06605v1 · Haris Angelidakis, Yury Makarychev, Vsevolod Oparin2016 · 9 citationsarXiv
An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut1611.05530v1 · Haris Angelidakis, Yury Makarychev, Pasin Manurangsi2016 · 12 citationsarXiv
Metric Perturbation Resilience1607.06442v1 · Konstantin Makarychev, Yury Makarychev2016 · 1 citationarXiv
Learning Communities in the Presence of Errors1511.03229v3 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2015 · 20 citationsarXiv
Satisfiability of Ordering CSPs Above Average1503.03851v2 · Konstantin Makarychev, Yury Makarychev, Yuan Zhou2015 · 0 citationsarXiv
A bi-criteria approximation algorithm for $k$ Means1507.04227v2 · Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko et al.2015 · 27 citationsarXivon Valency
Correlation Clustering with Noisy Partial Information1406.5667v2 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2014 · 5 citationsarXiv
Constant Factor Approximation for Balanced Cut in the PIE model1406.5665v1 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2014 · 18 citationsarXiv
Clustering, Hamming Embedding, Generalized LSH and the Max Norm1405.3167v1 · Behnam Neyshabur, Yury Makarychev, Nathan Srebro2014 · 7 citationsarXiv
Nonuniform Graph Partitioning with Unrelated Weights1401.0699v3 · Konstantin Makarychev, Yury Makarychev2014 · 1 citationarXiv
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion1404.4575v1 · Anand Louis, Yury Makarychev2014 · 14 citationsarXiv
The Power of Asymmetry in Binary Hashing1311.7662v1 · Behnam Neyshabur, Payman Yadollahpour, Yury Makarychev et al.2013 · 57 citationsarXiv
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut1305.1681v3 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2013 · 32 citationsarXiv
Planarizing an Unknown Surface1206.4898v1 · Yury Makarychev, Anastasios Sidiropoulos2012 · 1 citationarXiv
Approximation Algorithm for Non-Boolean MAX k-CSP1206.3603v1 · Konstantin Makarychev, Yury Makarychev2012 · 6 citationsarXiv
The Grothendieck constant is strictly smaller than Krivine's bound1103.6161v3 · Mark Braverman, Konstantin Makarychev, Yury Makarychev et al.2011 · 62 citationsarXiv
How to Play Unique Games against a Semi-Random Adversary1104.3806v1 · Alexandra Kolla, Konstantin Makarychev, Yury Makarychev2011 · 4 citationsarXiv
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability1006.4607v2 · Konstantin Makarychev, Yury Makarychev2010 · 15 citationsarXiv
On Graph Crossing Number and Edge Planarization1010.3976v1 · Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos2010 · 25 citationsarXiv
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers0912.1623v1 · Alexandra Kolla, Yury Makarychev, Amin Saberi et al.2009 · 53 citationsarXiv
Eigenvalue multiplicity and volume growth0806.1745v2 · James R. Lee, Yury Makarychev2008 · 13 citationsarXiv
How to Play Unique Games on Expanders0903.0367v1 · Konstantin Makarychev, Yury Makarychev2009 · 0 citationsarXiv
Dimension Reduction for the Hyperbolic Space0710.1343v1 · itai benjamini, Yury Makarychev2007 · 0 citationsarXiv
Conditionally independent random variablescs/0510029v1 · Konstantin Makarychev, Yury Makarychev2005 · 3 citationsarXiv
Career total: 131 works. 50 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.