Yury Makarychev

My Picture

My Picture

Yury Makarychev
	Professor Toyota Technological Institute at Chicago (TTIC)TTIC Professor (part-time appointment) Department of Computer Science and College University of Chicago
	Contact Information
	TTIC
	6045 S. Kenwood Ave.
	Chicago, IL 60637
	e-mail: yurdu

Teaching

Programming Requirement at TTIC (online presentation).

Winter 2020, Algorithms (TTIC 31010, CMSC 37000-1).

Winter 2019, Computational and Metric Geometry (TTIC 31100 and CMSC 39010-1).

Winter 2018, Algorithms (TTIC 31010, CMSC 37000-1).

Mini-course on metric geometry and its applications in Computer Science (Higher School of Economics, Moscow, Russia). Videos in Russian: 1 2 3.

PhD students: Jafar Jafarov, Naren Manoj (co-advised with Avrim Blum), and Max Ovsiankin.
Former PhD students: Haris Angelidakis (PhD 2018), now at ETH Zürich.

Selected Talks Available Online

1. k-means and k-medians under dimension reduction.: Workshop on Robust and High-Dimensional Statistics, The Simons Institute at UC Berkeley, November 2, 2018.; video slides
2. Metric Geometry and Its Applications in Computer Science.: Computer Science Club POMI, Russian Academy of Sciences, St. Petersburg, Russia, October 2017.; videos (in Russian)
3. Algorithms for Stable and Perturbation–Resilient Problems.: QTW Workshop on Beyond Worst Case Analysis, Northwestern University, May 2017.; slides video

Surveys

1. Perturbation Resilience,: Konstantin Makarychev, Yury Makarychev,; To appear in Beyond the Worst-Case Analysis of Algorithms, Tim Roughgarden (Ed.), Cambridge University Press.
2. Approximation Algorithms for CSPs (a survey of results),: Konstantin Makarychev, Yury Makarychev,; In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Zivny (Eds.), Dagstuhl Follow-Ups, vol. 7, 2017, pp. 287–325.
3. Bilu–Linial Stability (a survey on Bilu–Linial stability and perturbation resilience),: Konstantin Makarychev, Yury Makarychev,; In Perturbations, Optimization, and Statistics, T. Hazan, G. Papandreou, and D. Tarlow (Eds.), MIT Press, 2016.; You can download a draft copy of the survey here.

Publications

Correlation Clustering with Asymmetric Classification Errors,: Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev,; ICML 2020.
Regression via Kirszbraun Extension,: Armin Biess, Aryeh Kontorovich, Yury Makarychev, Hanan Zaichyk,; preprint arXiv:1905.11930.
Certified Algorithms: Worst-Case Analysis and Beyond,: Konstantin Makarychev, Yury Makarychev,; ITCS 2020.
Performance of Johnson–Lindenstrauss Transform for k-Means and k-Medians Clustering,: Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn,; STOC 2019. Invited to special issues of SICOMP and Theory of Computing.
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions,: Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn,; STOC 2018.
Algorithms for Stable and Perturbation–Resilient Problems,: Haris Angelidakis, Konstantin Makarychev, Yury Makarychev,; STOC 2017. Some results were reported in arXiv preprint Metric Perturbation Resilience.
An Improved Integrality Gap for the Călinescu–Karloff–Rabani Relaxation for Multiway Cut,: Haris Angelidakis, Yury Makarychev, Pasin Manurangsi; IPCO 2017.
Algorithmic and Hardness Results for the Hub Labeling Problem,: Haris Angelidakis, Yury Makarychev, Vsevolod Oparin,; SODA 2017.
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion,: Eden Chlamtáč, Michael Dinitz, Yury Makarychev,; SODA 2017.
Robust algorithms with polynomial loss for near-unanimity CSPs,: Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Opršal,; SODA 2017,; SIAM J. Comput. (SICOMP), vol. 48, no. 6, pp. 1763–1795 (2019).
A Union of Euclidean Metric Spaces is Euclidean,: Konstantin Makarychev, Yury Makarychev,; Discrete Analysis, 2016:14, 15 pp.; Slides for a talk at AMS Meeting, May 2017
Learning Communities in the Presence of Errors,: Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,; COLT 2016.
A bi-criteria approximation algorithm for k-Means,: Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward,; APPROX 2016.
Correlation Clustering with Noisy Partial Information,: Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,; COLT 2015.
Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable,: Konstantin Makarychev, Yury Makarychev, Yuan Zhou,; FOCS 2015.
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion,: Anand Louis, Yury Makarychev,; APPROX 2014,; Special issue of Theory of Computing, vol. 12, article 17, pp. 1–25, 2016.
Nonuniform Graph Partitioning with Unrelated Weights,: Konstantin Makarychev, Yury Makarychev,; ICALP 2014,; Sbornik: Mathematics (Russian Academy of Sciences), vol. 208, 2017.
Constant Factor Approximation for Balanced Cut in the PIE Model,: Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,; STOC 2014.
Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut,: Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,; SODA 2014.
Clustering, Hamming Embedding, Generalized LSH and the Max Norm,: Behnam Neyshabur, Yury Makarychev, Nathan Srebro,; ALT 2014.
A pseudo-approximation for the genus of Hamiltonian graphs,: Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos,; APPROX 2013,; Special issue of Theory of Computing, vol. 13, Article 5, pp. 1–47, 2017.
The Power of Asymmetry in Binary Hashing,: Behnam Neyshabur, Payman Yadollahpour, Yury Makarychev, Ruslan Salakhutdinov, Nathan Srebro,; NIPS 2013.
Sorting Noisy Data with Partial Information,: Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,; Innovations in Theoretical Computer Science, ITCS 2013.
Approximation Algorithm for Non-Boolean MAX k-CSP,: Konstantin Makarychev, Yury Makarychev,; APPROX 2012, pp. 254–265;; Theory of Computing, vol. 10, Article 13, pp. 341–358, 2014.
Planarizing an Unknown Surface,: Yury Makarychev, Anastasios Sidiropoulos,; APPROX 2012, pp. 266–275.
Approximation Algorithms for Semi-random Graph Partitioning Problems,: Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan,; STOC 2012, pp. 367–384.
Approximation Algorithms and Hardness of the k-Route Cut Problem,: Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou,; SODA 2012, pp. 780–799,; Special issue of ACM Transactions on Algorithms, vol. 12, no. 1, 2016.
Simple Linear Time Approximation Algorithm for Betweenness,: Yury Makarychev,; Operations Research Letters, vol. 40, no. 6, pp. 450–452, 2012.
Balanced Allocation: Memory Performance Tradeoffs,: Itai Benjamini, Yury Makarychev,; Annals of Applied Probability, vol. 22, no. 4, pp. 1642–1649, 2012.
The Grothendieck Constant is Strictly Smaller than Krivine's Bound,: Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor,; FOCS 2011, pp. 453–462;; Forum of Mathematics, Pi, vol. 1, e4, 2013.
How to Play Unique Games Against a Semi-Random Adversary,: Alexandra Kolla, Konstantin Makarychev, Yury Makarychev,; FOCS 2011, pp. 443–452.
Finding Almost-perfect Graph Bisections,: Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou,; Innovations in Computer Science, ICS 2011, pp. 321–337.
On Graph Crossing Number and Edge Planarization,: Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos,; SODA 2011, pp. 1050–1069.
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability,: Konstantin Makarychev, Yury Makarychev,; FOCS 2010, pp. 255–264.; Israel Journal of Mathematics, vol. 212, no. 2, pp. 913–959, 2016.
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers,: Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng,; STOC 2010, pp. 57–65.
How to Play Unique Games on Expanders,: Konstantin Makarychev, Yury Makarychev,; WAOA 2010, Lecture Notes in Computer Science, vol. 6534/2011, pp. 190–200, 2011.
Eigenvalue multiplicity and volume growth,: James R. Lee, Yury Makarychev,; preprint arXiv:0806.1745, 2008.
Integrality Gaps for Sherali-Adams Relaxations,: Moses Charikar, Konstantin Makarychev, Yury Makarychev,; STOC 2009, pp. 283–292.
Dimension Reduction for the Hyperbolic Space,: Itai Benjamini, Yury Makarychev,; Proc. Amer. Math. Soc. 137 (2009), pp. 695–698.
Local Global Tradeoffs in Metric Embeddings,: Moses Charikar, Konstantin Makarychev, Yury Makarychev,; FOCS 2007, pp. 713–723,; Special issue of SIAM J.Comput. (SICOMP), vol. 39, no. 6, pp. 2487–2512, 2010.
On the Advantage over Random for Maximum Acyclic Subgraph,: Moses Charikar, Konstantin Makarychev, Yury Makarychev,; FOCS 2007, pp. 625–633.
Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems,: Moses Charikar, Konstantin Makarychev, Yury Makarychev,; SODA 2007, pp. 62–68,; Special issue of ACM Transactions on Algorithms, vol. 5, no. 3, July 2009.
A Divide and Conquer Algorithm for d-Dimensional Arrangement,: Moses Charikar, Konstantin Makarychev, Yury Makarychev,; SODA 2007, pp. 541–546.
How to Play Unique Games Using Embeddings,: Eden Chlamtáč, Konstantin Makarychev, Yury Makarychev,; FOCS 2006, pp. 687–696.
Near-Optimal Algorithms for Unique Games,: Moses Charikar, Konstantin Makarychev, Yury Makarychev,; STOC 2006, pp. 205–214.
Directed Metrics and Directed Graph Partitioning Problems,: Moses Charikar, Konstantin Makarychev, Yury Makarychev,; SODA 2006, pp. 51–60.
O(sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems,: Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev,; STOC 2005, pp. 573–581.
Quadratic forms on graphs,: Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor,; STOC 2005, pp. 586–493,; Inventiones Mathematicae, vol. 163, no. 3, pp. 499–522, 2006.
Chain Independent Random Variables and Common Information,: Konstantin Makarychev, Yury Makarychev,; IEEE Transactions on Information Theory, 58(8), pp. 5279–5286, 2012.
A new class of non Shannon type inequalities for entropies,: K. Makarychev, Y. Makarychev, A. Romashchenko, N. Vereshchagin,; Communications in Information and Systems, vol. 2, no. 2, pp. 147–166, December 2002.
The Importance of Being Formal,: Konstantin Makarychev, Yury Makarychev,; The Mathematical Intelligencer, vol. 23 no. 1, 2001.
A Short Proof of Kuratowski's Graph Planarity Criterion,: Yury Makarychev,; The Journal of Graph Theory, vol. 25, pp. 129–131, 1997.
Proof of Pak's conjecture on tilings by T-tetrominoes (in Russian),: Konstantin Makarychev, Yury Makarychev,; Manuscript.