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 on High-Dimensional Analysis and Geometry

In the Spring quarter of 2022, Konstantin Makarychev and I organized workshops on clustering, massive data sets, and high-dimensional 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:

Former PhD students: 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. 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
arXiv preprint
 
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.