Y. Makarychev

Most-cited papers

O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
Amit Agarwal, M. Charikar, K. Makarychev, Y. Makarychev
2005Symposium on the Theory of Computing220 citations
Semantic Scholar
Local Global Tradeoffs in Metric Embeddings
Moses Charikar, K. Makarychev, Y. Makarychev
2010IEEE Annual Symposium on Foundations of Computer Science219 citations
Semantic Scholar
Near-optimal algorithms for unique games
M. Charikar, K. Makarychev, Y. Makarychev
2006Symposium on the Theory of Computing161 citations
Semantic Scholar
Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering
K. Makarychev, Y. Makarychev, Ilya P. Razenshteyn
2018Symposium on the Theory of Computing154 citations
Semantic Scholar
A new class of non-Shannon-type inequalities for entropies
K. Makarychev, Y. Makarychev, Andrei E. Romashchenko, N. Vereshchagin
2002Communications in Information and Systems145 citations Open access
Semantic Scholar
Integrality gaps for Sherali-Adams relaxations
M. Charikar, K. Makarychev, Y. Makarychev
2009Symposium on the Theory of Computing132 citations
Semantic Scholar
Quadratic forms on graphs
N. Alon, K. Makarychev, Y. Makarychev, A. Naor
2005Symposium on the Theory of Computing126 citations
Semantic Scholar
The Grothendieck Constant is Strictly Smaller than Krivine's Bound
M. Braverman, K. Makarychev, Y. Makarychev, A. Naor
2011IEEE Annual Symposium on Foundations of Computer Science105 citations Open access
Semantic Scholar
Near-optimal algorithms for maximum constraint satisfaction problems
M. Charikar, K. Makarychev, Y. Makarychev
2007ACM-SIAM Symposium on Discrete Algorithms93 citations
Semantic Scholar
Approximation algorithms for semi-random partitioning problems
K. Makarychev, Y. Makarychev, Aravindan Vijayaraghavan
2012Symposium on the Theory of Computing74 citations
Semantic Scholar
How to Play Unique Games Using Embeddings
E. Chlamtáč, K. Makarychev, Y. Makarychev
2006IEEE Annual Symposium on Foundations of Computer Science74 citations
Semantic Scholar
The Power of Asymmetry in Binary Hashing
Behnam Neyshabur, Payman Yadollahpour, Y. Makarychev, R. Salakhutdinov +1 more
2013Neural Information Processing Systems71 citations
Semantic Scholar
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
E. Chlamtáč, M. Dinitz, Y. Makarychev
2016ACM-SIAM Symposium on Discrete Algorithms70 citations Open access
Semantic Scholar
Subgraph sparsification and nearly optimal ultrasparsifiers
A. Kolla, Y. Makarychev, A. Saberi, S. Teng
2009Symposium on the Theory of Computing69 citations Open access
Semantic Scholar
Approximation Algorithms for Socially Fair Clustering
Y. Makarychev, A. Vakilian
2021Annual Conference Computational Learning Theory64 citations
Semantic Scholar
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut
K. Makarychev, Y. Makarychev, Aravindan Vijayaraghavan
2013ACM-SIAM Symposium on Discrete Algorithms59 citations
Semantic Scholar
Metric extension operators, vertex sparsifiers and Lipschitz extendability
K. Makarychev, Y. Makarychev
2010Israel Journal of Mathematics59 citations
Semantic Scholar
Algorithms for stable and perturbation-resilient problems
Haris Angelidakis, K. Makarychev, Y. Makarychev
2017Symposium on the Theory of Computing56 citations Open access
Semantic Scholar
Correlation Clustering with Noisy Partial Information
K. Makarychev, Y. Makarychev, Aravindan Vijayaraghavan
2014Annual Conference Computational Learning Theory49 citations
Semantic Scholar
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
A. Kolla, K. Makarychev, Y. Makarychev
2011IEEE Annual Symposium on Foundations of Computer Science46 citations
Semantic Scholar
A Bi-Criteria Approximation Algorithm for k-Means
K. Makarychev, Y. Makarychev, M. Sviridenko, Justin Ward
2015International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques43 citations
Semantic Scholar
How to Play Unique Games on Expanders
K. Makarychev, Y. Makarychev
2009Workshop on Approximation and Online Algorithms38 citations Open access
Semantic Scholar
Nonlinear dimension reduction via outer Bi-Lipschitz extensions
S. Mahabadi, K. Makarychev, Y. Makarychev, Ilya P. Razenshteyn
2018Symposium on the Theory of Computing37 citations
Semantic Scholar
Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion
Anand Louis, Y. Makarychev
2014Theory of Computing37 citations Open access
Semantic Scholar
Directed metrics and directed graph partitioning problems
M. Charikar, K. Makarychev, Y. Makarychev
2006ACM-SIAM Symposium on Discrete Algorithms37 citations
Semantic Scholar
Approximating Fair Clustering with Cascaded Norm Objectives
E. Chlamtáč, Y. Makarychev, A. Vakilian
2021ACM-SIAM Symposium on Discrete Algorithms35 citations Open access
Semantic Scholar
Approximation Algorithms and Hardness of the k-Route Cut Problem
Julia Chuzhoy, Y. Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2011TALG35 citations Open access
Semantic Scholar
Learning Communities in the Presence of Errors
K. Makarychev, Y. Makarychev, Aravindan Vijayaraghavan
2015Annual Conference Computational Learning Theory34 citations
Semantic Scholar
Approximation Algorithms for CSPs
K. Makarychev, Y. Makarychev
2017The Constraint Satisfaction Problem31 citations
Semantic Scholar
On the Advantage over Random for Maximum Acyclic Subgraph
M. Charikar, K. Makarychev, Y. Makarychev
2007IEEE Annual Symposium on Foundations of Computer Science30 citations
Semantic Scholar
An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut
Haris Angelidakis, Y. Makarychev, Pasin Manurangsi
2016Conference on Integer Programming and Combinatorial Optimization28 citations
Semantic Scholar
Constant factor approximation for balanced cut in the PIE model
K. Makarychev, Y. Makarychev, Aravindan Vijayaraghavan
2014Symposium on the Theory of Computing27 citations
Semantic Scholar
Sorting noisy data with partial information
K. Makarychev, Y. Makarychev, Aravindan Vijayaraghavan
2013Information Technology Convergence and Services25 citations
Semantic Scholar
Approximation Algorithm for Non-Boolean Max-k-CSP
K. Makarychev, Y. Makarychev
2012Theory of Computing25 citations Open access
Semantic Scholar
On graph crossing number and edge planarization
Julia Chuzhoy, Y. Makarychev, Anastasios Sidiropoulos
2010ACM-SIAM Symposium on Discrete Algorithms25 citations
Semantic Scholar
A short proof of Kuratowski's graph planarity criterion
Y. Makarychev
1997Journal of Graph Theory25 citations
Semantic Scholar
Robust algorithms with polynomial loss for near-unanimity CSPs
V. Dalmau, M. Kozik, A. Krokhin, K. Makarychev +2 more
2016ACM-SIAM Symposium on Discrete Algorithms17 citations Open access
Semantic Scholar
Simple linear time approximation algorithm for betweenness
Y. Makarychev
2012Operations Research Letters16 citations
Semantic Scholar
Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, K. Makarychev, Y. Makarychev
2020International Conference on Machine Learning15 citations
Semantic Scholar
Finding Almost-Perfect Graph Bisections
V. Guruswami, Y. Makarychev, P. Raghavendra, David Steurer +1 more
2011International Conference on Supercomputing15 citations
Semantic Scholar
Local Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, K. Makarychev, Y. Makarychev
2021International Conference on Machine Learning14 citations
Semantic Scholar
A divide and conquer algorithm for d-dimensional arrangement
M. Charikar, K. Makarychev, Y. Makarychev
2007ACM-SIAM Symposium on Discrete Algorithms13 citations
Semantic Scholar
Constraint Satisfaction Problems with Advice
Suprovat Ghoshal, K. Makarychev, Y. Makarychev
2024ACM-SIAM Symposium on Discrete Algorithms12 citations
Semantic Scholar
Fair Representation Clustering with Several Protected Classes
Zhen Dai, Y. Makarychev, A. Vakilian
2022Conference on Fairness, Accountability and Transparency12 citations Open access
Semantic Scholar
Algorithmic and Hardness Results for the Hub Labeling Problem
Haris Angelidakis, Y. Makarychev, Vsevolod Oparin
2016ACM-SIAM Symposium on Discrete Algorithms12 citations
Semantic Scholar
A Union of Euclidean Metric Spaces is Euclidean
K. Makarychev, Y. Makarychev
201610 citations Open access
Semantic Scholar
Nonuniform Graph Partitioning with Unrelated Weights
K. Makarychev, Y. Makarychev
2014International Colloquium on Automata, Languages and Programming9 citations Open access
Semantic Scholar
Stereoselectivity of halomethoxylation of 1-phenyltricyclo-[4.1.0.02,7]heptane and methyl 7-phenyltricyclo[4.1.0.02,7]-heptane-1-carboxylate
V. V. Razin, Y. Makarychev, R. N. Zolotarev, V. Vasin +2 more
20079 citations
Semantic Scholar
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
Y. Makarychev, N. Manoj, Max Ovsiankin
2022Annual Conference Computational Learning Theory7 citations Open access
Semantic Scholar
Certified Algorithms: Worst-Case Analysis and Beyond
K. Makarychev, Y. Makarychev
2020Information Technology Convergence and Services7 citations
Semantic Scholar