Yury Makarychev

My Picture

My Picture

Yury Makarychev
	I am an Associate Professor at Toyota Technological Institute at Chicago (TTIC)TTIC. I also hold a part-time appointment at the Department of Computer Science, University of Chicago.
	Ph.D. in computer science from Princeton University under the supervision of Moses Charikar M.S. in mathematics from Moscow State University graduated from Moscow Math High School #57
	Contact Information
	TTIC
	6045 S. Kenwood Ave.
	Chicago, IL 60637
	e-mail: yurdu

Teaching

Programming Requirement at TTIC (online presentation).

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

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

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

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

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

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

Summer 2014, REU: Semidefinite Programming and Constraint Satisfaction (with Madhur Tulsiani).

Winter 2014, Algorithms (TTIC 31010).

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

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

Fall 2010, Computational Geometry (TTIC 31100, CMSC 39000) (with Anastasios Sidiropoulos).

Former PhD students: Haris Angelidakis (PhD 2018), now at ETH Zürich.

Selected Talks

Upcoming: Performance of Johnson–Lindenstrauss Transform for k-Means and k-Medians Clustering

March 25: Theory of Computation Seminar, Harvard University

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. Lipschitz and outer bi-Lipschitz extensions.: Department of Mathematics, University of Notre Dame, March 21, 2018.; slides
3. Metric Geometry and Its Applications in Computer Science.: Computer Science Club POMI, Russian Academy of Sciences, St. Petersburg, Russia, October 2017.; videos (in Russian)
4. Algorithms for Stable and Perturbation–Resilient Problems.: QTW Workshop on Beyond Worst Case Analysis, Northwestern University, May 2017.; slides video
5. A Union of Euclidean Metric Spaces is Euclidean.: AMS Sectional Meeting, New York, NY, May 2017.; slides

Surveys

1. 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.
2. 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

Performance of Johnson–Lindenstrauss Transform for k-Means and k-Medians Clustering,: Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn,; STOC 2019, to appear.
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.
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.
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,; Journal of Topology and Analysis (to appear).
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.