Yury Makarychev

ORCID

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 49

Top Venues

Publications

Yury Makarychev, Max Ovsiankin, Erasmo Tani
-Group Steiner Tree. CoRR (2024)
Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA (2024)
Hananel Zaichyk, Armin Biess, Aryeh Kontorovich, Yury Makarychev
Efficient Kirszbraun extension with applications to regression. Math. Program. 207 (1) (2024)
Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
Constraint Satisfaction Problems with Advice. CoRR (2024)
Hananel Zaichyk, Armin Biess, Aryeh Kontorovich, Yury Makarychev
Correction: Efficient Kirszbraun extension with applications to regression. Math. Program. 207 (1) (2024)
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. STOC (2024)
Yury Makarychev, Max Ovsiankin, Erasmo Tani
-Group Steiner Tree. ICALP (2024)
Sayan Bandyapadhyay, Eden Chlamtác, Yury Makarychev, Ali Vakilian
A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering. CoRR (2024)
Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
Higher-Order Cheeger Inequality for Partitioning with Buffers. CoRR (2023)
Eden Chlamtác, Yury Makarychev, Ali Vakilian
Approximating Red-Blue Set Cover. CoRR (2023)
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
Approximation Algorithms for Norm Multiway Cut. CoRR (2023)
Eden Chlamtác, Yury Makarychev, Ali Vakilian
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment. APPROX/RANDOM (2023)
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. CoRR (2023)
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
Approximation Algorithm for Norm Multiway Cut. ESA (2023)
Zhen Dai, Yury Makarychev, Ali Vakilian
Fair Representation Clustering with Several Protected Classes. FAccT (2022)
Eden Chlamtác, Yury Makarychev, Ali Vakilian
Approximating Fair Clustering with Cascaded Norm Objectives. SODA (2022)
Zhen Dai, Yury Makarychev, Ali Vakilian
Fair Representation Clustering with Several Protected Classes. CoRR (2022)
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. CoRR (2022)
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. COLT (2022)
Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev
Two-Sided Kirszbraun Theorem. SoCG (2021)
Yury Makarychev, Ali Vakilian
Approximation Algorithms for Socially Fair Clustering. CoRR (2021)
Eden Chlamtác, Yury Makarychev, Ali Vakilian
Approximating Fair Clustering with Cascaded Norm Objectives. CoRR (2021)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Local Correlation Clustering with Asymmetric Classification Errors. ICML (2021)
Yury Makarychev, Ali Vakilian
Approximation Algorithms for Socially Fair Clustering. COLT (2021)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Local Correlation Clustering with Asymmetric Classification Errors. CoRR (2021)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Correlation Clustering with Asymmetric Classification Errors. CoRR (2021)
Konstantin Makarychev, Yury Makarychev
Certified Algorithms: Worst-Case Analysis and Beyond. ITCS (2020)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Correlation Clustering with Asymmetric Classification Errors. ICML (2020)
Armin Biess, Aryeh Kontorovich, Yury Makarychev, Hanan Zaichyk
Regression via Kirszbraun Extension with Applications to Imitation Learning. CoRR (2019)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. 48 (6) (2019)
Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
-medians clustering. STOC (2019)
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions. CoRR (2018)
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
Nonlinear dimension reduction via outer Bi-Lipschitz extensions. STOC (2018)
Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering. CoRR (2018)
Haris Angelidakis, Konstantin Makarychev, Yury Makarychev
Algorithms for stable and perturbation-resilient problems. STOC (2017)
Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos
A Pseudo-Approximation for the Genus of Hamiltonian Graphs. Theory Comput. 13 (1) (2017)
Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut. IPCO (2017)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. SODA (2017)
Eden Chlamtác, Michael Dinitz, Yury Makarychev
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. SODA (2017)
Haris Angelidakis, Yury Makarychev, Vsevolod Oparin
Algorithmic and Hardness Results for the Hub Labeling Problem. SODA (2017)
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
A Bi-Criteria Approximation Algorithm for k-Means. APPROX-RANDOM (2016)
Anand Louis, Yury Makarychev
Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion. Theory Comput. 12 (1) (2016)
Eden Chlamtác, Michael Dinitz, Yury Makarychev
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. CoRR (2016)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Learning Communities in the Presence of Errors. COLT (2016)
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
-Route Cut Problem. ACM Trans. Algorithms 12 (1) (2016)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR (2016)
Haris Angelidakis, Yury Makarychev, Vsevolod Oparin
Algorithmic and Hardness Results for the Hub Labeling Problem. CoRR (2016)
Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut. CoRR (2016)
Konstantin Makarychev, Yury Makarychev
Metric Perturbation Resilience. CoRR (2016)
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. FOCS (2015)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Correlation Clustering with Noisy Partial Information. COLT (2015)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Learning Communities in the Presence of Errors. CoRR (2015)
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
Satisfiability of Ordering CSPs Above Average. CoRR (2015)
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
A bi-criteria approximation algorithm for k Means. CoRR (2015)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. SODA (2014)
Behnam Neyshabur, Yury Makarychev, Nathan Srebro
Clustering, Hamming Embedding, Generalized LSH and the Max Norm. ALT (2014)
Behnam Neyshabur, Yury Makarychev, Nathan Srebro
Clustering, Hamming Embedding, Generalized LSH and the Max Norm. CoRR (2014)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Algorithms for Semi-random Correlation Clustering. CoRR (2014)
Anand Louis, Yury Makarychev
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. APPROX-RANDOM (2014)
Konstantin Makarychev, Yury Makarychev
-CSP. Theory Comput. 10 (2014)
Konstantin Makarychev, Yury Makarychev
Nonuniform Graph Partitioning with Unrelated Weights. ICALP (1) (2014)
Anand Louis, Yury Makarychev
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. CoRR (2014)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Constant Factor Approximation for Balanced Cut in the PIE model. CoRR (2014)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Constant factor approximation for balanced cut in the PIE model. STOC (2014)
Konstantin Makarychev, Yury Makarychev
Nonuniform Graph Partitioning with Unrelated Weights. CoRR (2014)
Behnam Neyshabur, Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour
The Power of Asymmetry in Binary Hashing. NIPS (2013)
Behnam Neyshabur, Payman Yadollahpour, Yury Makarychev, Ruslan Salakhutdinov, Nathan Srebro
The Power of Asymmetry in Binary Hashing. CoRR (2013)
Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos
A Pseudo-approximation for the Genus of Hamiltonian Graphs. APPROX-RANDOM (2013)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Sorting noisy data with partial information. ITCS (2013)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Bilu-Linial Stable Instances of Max Cut CoRR (2013)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Approximation algorithms for semi-random partitioning problems. STOC (2012)
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
-route cut problem. SODA (2012)
Yury Makarychev
Simple linear time approximation algorithm for betweenness. Oper. Res. Lett. 40 (6) (2012)
Konstantin Makarychev, Yury Makarychev
Approximation Algorithm for Non-boolean MAX k-CSP. APPROX-RANDOM (2012)
Yury Makarychev, Anastasios Sidiropoulos
Planarizing an Unknown Surface CoRR (2012)
Konstantin Makarychev, Yury Makarychev
Chain Independence and Common Information. IEEE Trans. Inf. Theory 58 (8) (2012)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Approximation Algorithms for Semi-random Graph Partitioning Problems CoRR (2012)
Konstantin Makarychev, Yury Makarychev
Approximation Algorithm for Non-Boolean MAX k-CSP CoRR (2012)
Yury Makarychev, Anastasios Sidiropoulos
Planarizing an Unknown Surface. APPROX-RANDOM (2012)
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
The Grothendieck constant is strictly smaller than Krivine's bound. CoRR (2011)
Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. FOCS (2011)
Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
How to Play Unique Games against a Semi-Random Adversary CoRR (2011)
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
Approximation Algorithms and Hardness of the k-Route Cut Problem CoRR (2011)
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
Finding Almost-Perfect Graph Bisections. ICS (2011)
Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos
On Graph Crossing Number and Edge Planarization. SODA (2011)
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
The Grothendieck Constant is Strictly Smaller than Krivine's Bound. FOCS (2011)
Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos
On Graph Crossing Number and Edge Planarization CoRR (2010)
Konstantin Makarychev, Yury Makarychev
How to Play Unique Games on Expanders. WAOA (2010)
Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng
Subgraph sparsification and nearly optimal ultrasparsifiers. STOC (2010)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Local Global Tradeoffs in Metric Embeddings. SIAM J. Comput. 39 (6) (2010)
Konstantin Makarychev, Yury Makarychev
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. FOCS (2010)
Konstantin Makarychev, Yury Makarychev
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability CoRR (2010)
Itai Benjamini, Yury Makarychev
Balanced Allocation: Memory Performance Tradeoffs CoRR (2009)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms 5 (3) (2009)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Integrality gaps for Sherali-Adams relaxations. STOC (2009)
Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers CoRR (2009)
Konstantin Makarychev, Yury Makarychev
How to Play Unique Games on Expanders CoRR (2009)
Konstantin Makarychev, Yury Makarychev
How to Play Unique Games on Expanders. Electron. Colloquium Comput. Complex. 16 (2009)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Near-optimal algorithms for maximum constraint satisfaction problems. SODA (2007)
Moses Charikar, Konstantin Makarychev, Yury Makarychev
-dimensional arrangement. SODA (2007)

Yury Makarychev.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Yury Makarychev