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

Workshops at IDEAL

In the Spring quarter of 2022, Konstantin Makarychev and I organized workshops on Algorithms for Massive Data Sets and High-Dimensional Analysis and Geometry. Video recordings are available online: videos of talks on clustering, videos of talks on massive data sets.

Teaching and Advising

Programming Requirement at TTIC (online presentation)

Spring 2025, Geometric Methods in Computer Science (TTIC 31100 and CMSC 39010-1)

Winter 2024, Algorithms (TTIC 31010, CMSC 37000-1)

Spring 2023, Computational and Metric Geometry (TTIC 31100 and CMSC 39010-1)

PhD students:

Naren Manoj (co-advised with Avrim Blum)
Max Ovsiankin
Keming Ouyang (co-advised with Madhur Tulsiani)
Omshi Samal (co-advised with Madhur Tulsiani)

Former PhD students:

Haris Angelidakis (PhD 2018) → ETH Zürich → CoW Protocol
Jafar Jafarov (PhD 2022) → Meta/Facebook → Brevan Howard.

Postdocs: Suprovat Ghoshal (co-mentored with Konstantin Makarychev)
Former postdocs: Ali Vakilian (IDEAL Postdoctoral Scholar)

Selected Presentations and Talks Available Online

1. Beyond worst-case analysis of algorithms and algorithmic fairness: A mini-course at ADFOCS 2023, The Max Planck Institute for Informatics, August 2023; slides
2. Approximation algorithms for the socially fair clustering problem: Research at TTIC, May 2022; video
3. 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
4. Algorithms for Stable and Perturbation-Resilient Problems: QTW Workshop on Beyond Worst Case Analysis, Northwestern University, May 2017; video slides

Surveys

1. Perturbation Resilience: Konstantin Makarychev, Yury Makarychev; 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

Publications

A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering: Sayan Bandyapadhyay, Eden Chlamtáč, Zachary Friggstad, Mahya Jamshidian, Yury Makarychev, Ali Vakilian; arXiv preprint
Constraint Satisfaction Problems with Advice: Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev; SODA 2025
Approximation Algorithms for ℓ_p-Shortest Path and ℓ_p-Group Steiner Tree: Yury Makarychev, Max Ovsiankin, Erasmo Tani; ICALP 2024
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes: Yury Makarychev, Naren Manoj, Max Ovsiankin; STOC 2024
Higher-Order Cheeger Inequality for Partitioning with Buffers: Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan; SODA 2024
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment: Eden Chlamtáč, Yury Makarychev, Ali Vakilian; APPROX 2023
Approximation Algorithm for Norm Multiway Cut: Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan; ESA 2023
Efficient Kirszbraun Extension with Applications to Regression: Hanan Zaichyk, Armin Biess, Aryeh Kontorovich, Yury Makarychev; Mathematical Programming 2023
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes: Yury Makarychev, Naren Manoj, Max Ovsiankin; COLT 2022
Fair Representation Clustering with Several Protected Classes: Zhen Dai, Yury Makarychev, Ali Vakilian; FAccT 2022
Approximating Fair Clustering with Cascaded Norm Objectives: Eden Chlamtáč, Yury Makarychev, Ali Vakilian; SODA 2022
Local Correlation Clustering with Asymmetric Classification Errors: Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev; ICML 2021
Approximation Algorithms for Socially Fair Clustering: Yury Makarychev, Ali Vakilian; COLT 2021
Two-sided Kirszbraun Theorem: Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev; SoCG 2021
Correlation Clustering with Asymmetric Classification Errors: Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev; ICML 2020
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.
Chain Independent Random Variables and Common Information: Konstantin Makarychev, Yury Makarychev; IEEE Transactions on Information Theory, 58(8), pp. 5279–5286, 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
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