Yury Makarychev

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

For Ukrainian Students

If you are looking for a summer internship or PhD position in theoretical computer science, please contact me.

Workshop on High-Dimensional Analysis and Geometry

If you'd like to learn about new and exciting results on clustering, massive data sets, and high-dimensional geometry, please join Konstantin Makarychev and me for our upcoming workshops. The workshops will take place at Northwestern University on April 22, April 23, May 13, and May 27. Both in-person and remote participants are welcome!
(videos of talks on clustering, videos of talks on massive data sets)

Teaching

Programming Requirement at TTIC (online presentation).

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

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

PhD students: Naren Manoj (co-advised with Avrim Blum) and Max Ovsiankin.
Former PhD students: Haris Angelidakis (PhD 2018) → ETH Zürich → CoW Protocol and Jafar Jafarov (PhD 2022) → Meta/Facebook.
Postdocs: Ali Vakilian (IDEAL Postdoctoral Scholar)

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. 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,; 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

Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes: Yury Makarychev, Naren Manoj, Max Ovsiankin; COLT 2022, to appear.
Fair Representation Clustering with Several Protected Classes: Zhen Dai, Yury Makarychev, Ali Vakilian; FAccT 2022, to appear.
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.
Regression via Kirszbraun Extension,: Armin Biess, Aryeh Kontorovich, Yury Makarychev, Hanan Zaichyk,; preprint arXiv:1905.11930.
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.