Yury Makarychev

124 papers A* 40A 6B 3Journal 65Unranked 8

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs. CoRR Yury Makarychev
2026	A*	`conf`	Hardness of Approximation for Shortest Path with Vector Costs. SODA Charlie Carlson, Yury Makarychev, Ron Mosenzon
2025	A*	`conf`	Constraint Satisfaction Problems with Advice. SODA Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
2025	J	`jnl`	Hardness of Approximation for Shortest Path with Vector Costs. CoRR Charlie Carlson, Yury Makarychev, Ron Mosenzon
2025	A	`conf`	Max-Cut with Multiple Cardinality Constraints. APPROX/RANDOM Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian
2025	J	`jnl`	Max-Cut with Multiple Cardinality Constraints. CoRR Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian
2024	J	`jnl`	A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering. CoRR Sayan Bandyapadhyay, Eden Chlamtác, Yury Makarychev, Ali Vakilian
2024	J	`jnl`	Approximation Algorithms for ℓ CoRR Yury Makarychev, Max Ovsiankin, Erasmo Tani
2024	A*	`conf`	Approximation Algorithms for 𝓁 ICALP Yury Makarychev, Max Ovsiankin, Erasmo Tani
2024	J	`jnl`	Constraint Satisfaction Problems with Advice. CoRR Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
2024	J	`jnl`	Correction: Efficient Kirszbraun extension with applications to regression. Math. Program. Hananel Zaichyk, Armin Biess, Aryeh Kontorovich, Yury Makarychev
2024	J	`jnl`	Efficient Kirszbraun extension with applications to regression. Math. Program. Hananel Zaichyk, Armin Biess, Aryeh Kontorovich, Yury Makarychev
2024	A*	`conf`	Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
2024	A*	`conf`	Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. STOC Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
2023	A	`conf`	Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment. APPROX/RANDOM Eden Chlamtác, Yury Makarychev, Ali Vakilian
2023	J	`jnl`	Approximating Red-Blue Set Cover. CoRR Eden Chlamtác, Yury Makarychev, Ali Vakilian
2023	A	`conf`	Approximation Algorithm for Norm Multiway Cut. ESA Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
2023	J	`jnl`	Approximation Algorithms for Norm Multiway Cut. CoRR Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
2023	J	`jnl`	Higher-Order Cheeger Inequality for Partitioning with Buffers. CoRR Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
2023	J	`jnl`	Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. CoRR Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
2022	A*	`conf`	Approximating Fair Clustering with Cascaded Norm Objectives. SODA Eden Chlamtác, Yury Makarychev, Ali Vakilian
2022	—	`conf`	Fair Representation Clustering with Several Protected Classes. FAccT Zhen Dai, Yury Makarychev, Ali Vakilian
2022	J	`jnl`	Fair Representation Clustering with Several Protected Classes. CoRR Zhen Dai, Yury Makarychev, Ali Vakilian
2022	A*	`conf`	Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. COLT Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
2022	J	`jnl`	Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. CoRR Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
2021	J	`jnl`	Approximating Fair Clustering with Cascaded Norm Objectives. CoRR Eden Chlamtác, Yury Makarychev, Ali Vakilian
2021	A*	`conf`	Approximation Algorithms for Socially Fair Clustering. COLT Yury Makarychev, Ali Vakilian
2021	J	`jnl`	Approximation Algorithms for Socially Fair Clustering. CoRR Yury Makarychev, Ali Vakilian
2021	J	`jnl`	Correlation Clustering with Asymmetric Classification Errors. CoRR Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2021	A*	`conf`	Local Correlation Clustering with Asymmetric Classification Errors. ICML Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2021	J	`jnl`	Local Correlation Clustering with Asymmetric Classification Errors. CoRR Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2021	A*	`conf`	Two-Sided Kirszbraun Theorem. SoCG Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev
2020	A	`conf`	Certified Algorithms: Worst-Case Analysis and Beyond. ITCS Konstantin Makarychev, Yury Makarychev
2020	A*	`conf`	Correlation Clustering with Asymmetric Classification Errors. ICML Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2020	—	`ch.`	Perturbation Resilience. Beyond the Worst-Case Analysis of Algorithms Konstantin Makarychev, Yury Makarychev
2020	A*	`ed.`	Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 STOC Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
2019	J	`jnl`	Performance of Johnson-Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering. SIAM J. Comput. Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2019	A*	`conf`	Performance of Johnson-Lindenstrauss transform for STOC Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2019	J	`jnl`	Regression via Kirszbraun Extension with Applications to Imitation Learning. CoRR Armin Biess, Aryeh Kontorovich, Yury Makarychev, Hanan Zaichyk
2019	J	`jnl`	Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2018	J	`jnl`	Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions. CoRR Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2018	A*	`conf`	Nonlinear dimension reduction via outer Bi-Lipschitz extensions. STOC Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2018	J	`jnl`	Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering. CoRR Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2017	J	`jnl`	A Pseudo-Approximation for the Genus of Hamiltonian Graphs. Theory Comput. Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos
2017	A*	`conf`	Algorithmic and Hardness Results for the Hub Labeling Problem. SODA Haris Angelidakis, Yury Makarychev, Vsevolod Oparin
2017	A*	`conf`	Algorithms for stable and perturbation-resilient problems. STOC Haris Angelidakis, Konstantin Makarychev, Yury Makarychev
2017	B	`conf`	An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut. IPCO Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
2017	—	`ch.`	Approximation Algorithms for CSPs. The Constraint Satisfaction Problem Konstantin Makarychev, Yury Makarychev
2017	A*	`conf`	Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. SODA Eden Chlamtác, Michael Dinitz, Yury Makarychev
2017	A*	`conf`	Robust algorithms with polynomial loss for near-unanimity CSPs. SODA Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2016	—	`conf`	A Bi-Criteria Approximation Algorithm for k-Means. APPROX-RANDOM Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
2016	J	`jnl`	Algorithmic and Hardness Results for the Hub Labeling Problem. CoRR Haris Angelidakis, Yury Makarychev, Vsevolod Oparin
2016	J	`jnl`	An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut. CoRR Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
2016	J	`jnl`	Approximation Algorithms and Hardness of the ACM Trans. Algorithms Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2016	J	`jnl`	Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion. Theory Comput. Anand Louis, Yury Makarychev
2016	A*	`conf`	Learning Communities in the Presence of Errors. COLT Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2016	J	`jnl`	Metric Perturbation Resilience. CoRR Konstantin Makarychev, Yury Makarychev
2016	J	`jnl`	Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. CoRR Eden Chlamtác, Michael Dinitz, Yury Makarychev
2016	J	`jnl`	Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2015	J	`jnl`	A bi-criteria approximation algorithm for k Means. CoRR Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
2015	A*	`conf`	Correlation Clustering with Noisy Partial Information. COLT Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2015	J	`jnl`	Learning Communities in the Presence of Errors. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2015	J	`jnl`	Satisfiability of Ordering CSPs Above Average. CoRR Konstantin Makarychev, Yury Makarychev, Yuan Zhou
2015	A*	`conf`	Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. FOCS Konstantin Makarychev, Yury Makarychev, Yuan Zhou
2014	J	`jnl`	Algorithms for Semi-random Correlation Clustering. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	J	`jnl`	Approximation Algorithm for Non-Boolean Max- Theory Comput. Konstantin Makarychev, Yury Makarychev
2014	—	`conf`	Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. APPROX-RANDOM Anand Louis, Yury Makarychev
2014	J	`jnl`	Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. CoRR Anand Louis, Yury Makarychev
2014	A*	`conf`	Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. SODA Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	B	`conf`	Clustering, Hamming Embedding, Generalized LSH and the Max Norm. ALT Behnam Neyshabur, Yury Makarychev, Nathan Srebro
2014	J	`jnl`	Clustering, Hamming Embedding, Generalized LSH and the Max Norm. CoRR Behnam Neyshabur, Yury Makarychev, Nathan Srebro
2014	J	`jnl`	Constant Factor Approximation for Balanced Cut in the PIE model. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	A*	`conf`	Constant factor approximation for balanced cut in the PIE model. STOC Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	—	`conf`	Nonuniform Graph Partitioning with Unrelated Weights. ICALP (1) Konstantin Makarychev, Yury Makarychev
2014	J	`jnl`	Nonuniform Graph Partitioning with Unrelated Weights. CoRR Konstantin Makarychev, Yury Makarychev
2013	—	`conf`	A Pseudo-approximation for the Genus of Hamiltonian Graphs. APPROX-RANDOM Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos
2013	J	`jnl`	Bilu-Linial Stable Instances of Max Cut CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2013	A	`conf`	Sorting noisy data with partial information. ITCS Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2013	—	`conf`	The Power of Asymmetry in Binary Hashing. NIPS Behnam Neyshabur, Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour
2013	J	`jnl`	The Power of Asymmetry in Binary Hashing. CoRR Behnam Neyshabur, Payman Yadollahpour, Yury Makarychev, Ruslan Salakhutdinov, Nathan Srebro
2012	J	`jnl`	Approximation Algorithm for Non-Boolean MAX k-CSP CoRR Konstantin Makarychev, Yury Makarychev
2012	—	`conf`	Approximation Algorithm for Non-boolean MAX k-CSP. APPROX-RANDOM Konstantin Makarychev, Yury Makarychev
2012	J	`jnl`	Approximation Algorithms for Semi-random Graph Partitioning Problems CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2012	A*	`conf`	Approximation algorithms and hardness of the SODA Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2012	A*	`conf`	Approximation algorithms for semi-random partitioning problems. STOC Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2012	J	`jnl`	Chain Independence and Common Information. IEEE Trans. Inf. Theory Konstantin Makarychev, Yury Makarychev
2012	J	`jnl`	Planarizing an Unknown Surface CoRR Yury Makarychev, Anastasios Sidiropoulos
2012	—	`conf`	Planarizing an Unknown Surface. APPROX-RANDOM Yury Makarychev, Anastasios Sidiropoulos
2012	J	`jnl`	Simple linear time approximation algorithm for betweenness. Oper. Res. Lett. Yury Makarychev
2011	J	`jnl`	Approximation Algorithms and Hardness of the k-Route Cut Problem CoRR Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2011	A	`conf`	Finding Almost-Perfect Graph Bisections. ICS Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
2011	A*	`conf`	How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. FOCS Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
2011	J	`jnl`	How to Play Unique Games against a Semi-Random Adversary CoRR Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
2011	A*	`conf`	On Graph Crossing Number and Edge Planarization. SODA Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos
2011	A*	`conf`	The Grothendieck Constant is Strictly Smaller than Krivine's Bound. FOCS Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2011	J	`jnl`	The Grothendieck constant is strictly smaller than Krivine's bound. CoRR Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2010	B	`conf`	How to Play Unique Games on Expanders. WAOA Konstantin Makarychev, Yury Makarychev
2010	J	`jnl`	Local Global Tradeoffs in Metric Embeddings. SIAM J. Comput. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2010	J	`jnl`	Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability CoRR Konstantin Makarychev, Yury Makarychev
2010	A*	`conf`	Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. FOCS Konstantin Makarychev, Yury Makarychev
2010	J	`jnl`	On Graph Crossing Number and Edge Planarization CoRR Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos
2010	A*	`conf`	Subgraph sparsification and nearly optimal ultrasparsifiers. STOC Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng
2009	J	`jnl`	Balanced Allocation: Memory Performance Tradeoffs CoRR Itai Benjamini, Yury Makarychev
2009	J	`jnl`	How to Play Unique Games on Expanders CoRR Konstantin Makarychev, Yury Makarychev
2009	J	`jnl`	How to Play Unique Games on Expanders. Electron. Colloquium Comput. Complex. Konstantin Makarychev, Yury Makarychev
2009	A*	`conf`	Integrality gaps for Sherali-Adams relaxations. STOC Moses Charikar, Konstantin Makarychev, Yury Makarychev
2009	J	`jnl`	Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms Moses Charikar, Konstantin Makarychev, Yury Makarychev
2009	J	`jnl`	Subgraph Sparsification and Nearly Optimal Ultrasparsifiers CoRR Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng
2007	A*	`conf`	A divide and conquer algorithm for SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	Local Global Tradeoffs in Metric Embeddings. FOCS Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	J	`jnl`	Local Global Tradeoffs in Metric Embeddings. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	Near-optimal algorithms for maximum constraint satisfaction problems. SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	On the Advantage over Random for Maximum Acyclic Subgraph. FOCS Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	J	`jnl`	On the Advantage over Random for Maximum Acyclic Subgraph. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	J	`jnl`	Approximation Algorithm for the Max k-CSP Problem. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	A*	`conf`	Directed metrics and directed graph partitioning problems. SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	A*	`conf`	How to Play Unique Games Using Embeddings. FOCS Eden Chlamtac, Konstantin Makarychev, Yury Makarychev
2006	A*	`conf`	Near-optimal algorithms for unique games. STOC Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	J	`jnl`	Note on MAX 2SAT. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2005	J	`jnl`	Conditionally independent random variables CoRR Konstantin Makarychev, Yury Makarychev
2005	A*	`conf`	O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. STOC Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev
2005	A*	`conf`	Quadratic forms on graphs. STOC Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2002	J	`jnl`	A new class of non-Shannon-type inequalities for entropies. Commun. Inf. Syst. Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai K. Vereshchagin
1997	J	`jnl`	A short proof of Kuratowski's graph planarity criterion. J. Graph Theory Yury Makarychev