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)

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áč, Yury Makarychev, Ali Vakilian; arXiv preprint
Constraint Satisfaction Problems with Advice: Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev; SODA 2025 (to appear)
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