Yury Makarychev

According to our database, Yury Makarychev authored at least 79 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Correction: Efficient Kirszbraun extension with applications to regression.

Hananel Zaichyk, Armin Biess, Aryeh Kontorovich, Yury Makarychev

Math. Program., September, 2024

Efficient Kirszbraun extension with applications to regression.

Hananel Zaichyk, Armin Biess, Aryeh Kontorovich, Yury Makarychev

Math. Program., September, 2024

A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering.

Sayan Bandyapadhyay, Eden Chlamtác, Yury Makarychev, Ali Vakilian

CoRR, 2024

Constraint Satisfaction Problems with Advice.

Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev

CoRR, 2024

Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes.

Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Higher-Order Cheeger Inequality for Partitioning with Buffers.

Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Approximation Algorithms for 𝓁_p-Shortest Path and 𝓁_p-Group Steiner Tree.

Yury Makarychev, Max Ovsiankin, Erasmo Tani

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Approximation Algorithms for Norm Multiway Cut.

Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan

CoRR, 2023

Approximating Red-Blue Set Cover.

Eden Chlamtác, Yury Makarychev, Ali Vakilian

CoRR, 2023

Approximation Algorithm for Norm Multiway Cut.

Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment.

Eden Chlamtác, Yury Makarychev, Ali Vakilian

Proceedings of the Approximation, 2023

2022

Approximating Fair Clustering with Cascaded Norm Objectives.

Eden Chlamtác, Yury Makarychev, Ali Vakilian

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Fair Representation Clustering with Several Protected Classes.

Zhen Dai, Yury Makarychev, Ali Vakilian

Proceedings of the FAccT '22: 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul, Republic of Korea, June 21, 2022

Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes.

Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Local Correlation Clustering with Asymmetric Classification Errors.

Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev

Proceedings of the 38th International Conference on Machine Learning, 2021

Two-Sided Kirszbraun Theorem.

Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev

Proceedings of the 37th International Symposium on Computational Geometry, 2021

Approximation Algorithms for Socially Fair Clustering.

Yury Makarychev, Ali Vakilian

Proceedings of the Conference on Learning Theory, 2021

2020

Certified Algorithms: Worst-Case Analysis and Beyond.

Konstantin Makarychev, Yury Makarychev

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Correlation Clustering with Asymmetric Classification Errors.

Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev

Proceedings of the 37th International Conference on Machine Learning, 2020

Perturbation Resilience.

Konstantin Makarychev, Yury Makarychev

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

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

Regression via Kirszbraun Extension with Applications to Imitation Learning.

Armin Biess, Aryeh Kontorovich, Yury Makarychev, Hanan Zaichyk

CoRR, 2019

Performance of Johnson-Lindenstrauss transform for <i>k</i>-means and <i>k</i>-medians clustering.

Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering.

Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn

CoRR, 2018

Nonlinear dimension reduction via outer Bi-Lipschitz extensions.

Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

A Pseudo-Approximation for the Genus of Hamiltonian Graphs.

Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos

Theory Comput., 2017

Algorithms for stable and perturbation-resilient problems.

Haris Angelidakis, Konstantin Makarychev, Yury Makarychev

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion.

Eden Chlamtác, Michael Dinitz, Yury Makarychev

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Algorithmic and Hardness Results for the Hub Labeling Problem.

Haris Angelidakis, Yury Makarychev, Vsevolod Oparin

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut.

Haris Angelidakis, Yury Makarychev, Pasin Manurangsi

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Approximation Algorithms for CSPs.

Konstantin Makarychev, Yury Makarychev

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion.

Anand Louis, Yury Makarychev

Theory Comput., 2016

Approximation Algorithms and Hardness of the <i>k</i>-Route Cut Problem.

Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou

ACM Trans. Algorithms, 2016

Metric Perturbation Resilience.

Konstantin Makarychev, Yury Makarychev

CoRR, 2016

Learning Communities in the Presence of Errors.

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Proceedings of the 29th Conference on Learning Theory, 2016

A Bi-Criteria Approximation Algorithm for k-Means.

Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward

Proceedings of the Approximation, 2016

2015

Satisfiability of Ordering CSPs Above Average.

Konstantin Makarychev, Yury Makarychev, Yuan Zhou

CoRR, 2015

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable.

Konstantin Makarychev, Yury Makarychev, Yuan Zhou

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Correlation Clustering with Noisy Partial Information.

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Approximation Algorithm for Non-Boolean Max-<i>k</i>-CSP.

Konstantin Makarychev, Yury Makarychev

Theory Comput., 2014

Algorithms for Semi-random Correlation Clustering.

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

CoRR, 2014

Constant factor approximation for balanced cut in the PIE model.

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Proceedings of the Symposium on Theory of Computing, 2014

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut.

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Nonuniform Graph Partitioning with Unrelated Weights.

Konstantin Makarychev, Yury Makarychev

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Clustering, Hamming Embedding, Generalized LSH and the Max Norm.

Behnam Neyshabur, Yury Makarychev, Nathan Srebro

Proceedings of the Algorithmic Learning Theory - 25th International Conference, 2014

2013

Bilu-Linial Stable Instances of Max Cut

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

CoRR, 2013

The Power of Asymmetry in Binary Hashing.

Behnam Neyshabur, Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Sorting noisy data with partial information.

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Chain Independence and Common Information.

Konstantin Makarychev, Yury Makarychev

IEEE Trans. Inf. Theory, 2012

Simple linear time approximation algorithm for betweenness.

Yury Makarychev

Oper. Res. Lett., 2012

Approximation Algorithms for Semi-random Graph Partitioning Problems

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

CoRR, 2012

Approximation algorithms for semi-random partitioning problems.

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Planarizing an Unknown Surface.

Yury Makarychev, Anastasios Sidiropoulos

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

Approximation Algorithm for Non-boolean MAX k-CSP.

Konstantin Makarychev, Yury Makarychev

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Approximation Algorithms and Hardness of the k-Route Cut Problem

Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou

CoRR, 2011

How to Play Unique Games against a Semi-Random Adversary

Alexandra Kolla, Konstantin Makarychev, Yury Makarychev

CoRR, 2011

On Graph Crossing Number and Edge Planarization.

Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Finding Almost-Perfect Graph Bisections.

Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou

Proceedings of the Innovations in Computer Science, 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

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

The Grothendieck Constant is Strictly Smaller than Krivine's Bound.

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Local Global Tradeoffs in Metric Embeddings.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

SIAM J. Comput., 2010

Subgraph sparsification and nearly optimal ultrasparsifiers.

Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability.

Konstantin Makarychev, Yury Makarychev

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Near-optimal algorithms for maximum constraint satisfaction problems.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

ACM Trans. Algorithms, 2009

How to Play Unique Games on Expanders.

Konstantin Makarychev, Yury Makarychev

Electron. Colloquium Comput. Complex., 2009

Balanced Allocation: Memory Performance Tradeoffs

Itai Benjamini, Yury Makarychev

CoRR, 2009

Integrality gaps for Sherali-Adams relaxations.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2007

On the Advantage over Random for Maximum Acyclic Subgraph.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Electron. Colloquium Comput. Complex., 2007

A divide and conquer algorithm for <i>d</i>-dimensional arrangement.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Note on MAX 2SAT.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Electron. Colloquium Comput. Complex., 2006

Approximation Algorithm for the Max k-CSP Problem.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Electron. Colloquium Comput. Complex., 2006

Near-optimal algorithms for unique games.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Directed metrics and directed graph partitioning problems.

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

How to Play Unique Games Using Embeddings.

Eden Chlamtac, Konstantin Makarychev, Yury Makarychev

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Conditionally independent random variables

Konstantin Makarychev, Yury Makarychev

CoRR, 2005

Quadratic forms on graphs.

Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.

Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2002

A new class of non-Shannon-type inequalities for entropies.

Konstantin Makarychev, Yury Makarychev, Andrei E. Romashchenko, Nikolai K. Vereshchagin

Commun. Inf. Syst., 2002

1997

A short proof of Kuratowski's graph planarity criterion.

Yury Makarychev

J. Graph Theory, 1997