O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems A Agarwal, M Charikar, K Makarychev, Y Makarychev Proceedings of the thirty-seventh annual ACM symposium on Theory of …, 2005 | 193 | 2005 |
Near-optimal algorithms for unique games M Charikar, K Makarychev, Y Makarychev Proceedings of the thirty-eighth annual ACM symposium on Theory of computing …, 2006 | 151 | 2006 |
A new class of non-Shannon-type inequalities for entropies K Makarychev, Y Makarychev, A Romashchenko, N Vereshchagin Communications in Information and Systems 2 (2), 147-166, 2002 | 132 | 2002 |
Integrality gaps for Sherali-Adams relaxations M Charikar, K Makarychev, Y Makarychev Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009 | 124 | 2009 |
Quadratic forms on graphs N Alon, K Makarychev, Y Makarychev, A Naor Inventiones mathematicae 163 (3), 499-522, 2006 | 88 | 2006 |
Near-optimal algorithms for maximum constraint satisfaction problems M Charikar, K Makarychev, Y Makarychev ACM Transactions on Algorithms (TALG) 5 (3), 32, 2009 | 87 | 2009 |
The Grothendieck constant is strictly smaller than Krivine’s bound M Braverman, K Makarychev, Y Makarychev, A Naor Forum of Mathematics, Pi 1, 2013 | 80 | 2013 |
How to play unique games using embeddings E Chlamtac, K Makarychev, Y Makarychev 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06 …, 2006 | 70 | 2006 |
Subgraph sparsification and nearly optimal ultrasparsifiers A Kolla, Y Makarychev, A Saberi, SH Teng Proceedings of the forty-second ACM symposium on Theory of computing, 57-66, 2010 | 64 | 2010 |
Approximation algorithms for semi-random partitioning problems K Makarychev, Y Makarychev, A Vijayaraghavan Proceedings of the forty-fourth annual ACM symposium on Theory of computing …, 2012 | 60 | 2012 |
The power of asymmetry in binary hashing B Neyshabur, N Srebro, RR Salakhutdinov, Y Makarychev, ... Advances in Neural Information Processing Systems 26, 2823-2831, 2013 | 53 | 2013 |
Bilu-Linial stable instances of max cut and minimum multiway cut K Makarychev, Y Makarychev, A Vijayaraghavan Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete …, 2014 | 52 | 2014 |
Metric extension operators, vertex sparsifiers and Lipschitz extendability K Makarychev, Y Makarychev Israel Journal of Mathematics 212 (2), 913-959, 2016 | 51* | 2016 |
Algorithms for stable and perturbation-resilient problems H Angelidakis, K Makarychev, Y Makarychev Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 46 | 2017 |
Quadratic forms on graphs N Alon, K Makarychev, Y Makarychev, A Naor Proceedings of the thirty-seventh annual ACM symposium on Theory of …, 2005 | 43 | 2005 |
How to play unique games against a semi-random adversary: Study of semi-random models of unique games A Kolla, K Makarychev, Y Makarychev 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 443-452, 2011 | 39 | 2011 |
A Bi-Criteria Approximation Algorithm for k-Means K Makarychev, Y Makarychev, M Sviridenko, J Ward Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2016 | 37 | 2016 |
Approximation Algorithms and Hardness of the k-Route Cut Problem J Chuzhoy, Y Makarychev, A Vijayaraghavan, Y Zhou ACM Transactions on Algorithms (TALG) 12 (1), 1-40, 2015 | 36 | 2015 |
Directed metrics and directed graph partitioning problems M Charikar, K Makarychev, Y Makarychev SODA 6, 51-60, 2006 | 33 | 2006 |
Correlation Clustering with Noisy Partial Information K Makarychev, Y Makarychev, A Vijayaraghavan Proceedings of the Conference on Learning Theory (COLT) 6, 2015 | 31 | 2015 |