Euiwoong Lee
I am an assistant professor in the Computer Science and Engineering Division at the University of Michigan.
Previously, I was a postdoc at New York University hosted by Oded Regev and Subhash Khot,
and a research fellow at Simons Institute for the Theory of Computing.
I received my PhD from Carnegie Mellon University, where I was advised by Venkatesan Guruswami
and my thesis
won the Edmund M. Clarke Doctoral Dissertation Award.
I was supported by Samsung Scholarship
and
Simons Award for Graduate Students in TCS.
Email
(First name with eight letters) at umich dot edu
Teaching
EECS 598-010. Approximation algorithms and Hardness of approximation. Fall '20 and Fall '22:
Course notes transcribed by Pingbang Hu.
EECS 498-004: Algorithms for Data Science. Winter '22.
EECS 477: Introduction to Algorithms. Fall '23 and Winter '24
EECS 376: Foundations of Computer Science. Fall '21 and Winter '23.
EECS 586: Design and Analysis of Algorithms. Winter '21.
Interests and Current Research
Approximation algorithms and Hardness of approximation
Connection between discrete and continuous optimization
Convex hierarchies (e.g., Sum-of-Squares, Sherali-Adams)
Parameterized complexity
Postdocs
Suprovat Ghoshal (2020 - 2022)
Neng Huang (2024 - ) (co-advising with Nikhil Bansal)
PhD Students
Anthony Della Pella (co-advising with Martin Strauss)
Aditya Anand
Amatya Sharma (co-advising with Nikhil Bansal)
Publications
Understanding the Cluster Linear Program for Correlation Clustering
with
Nairen Cao and
Vincent Cohen-Addad and
Shi Li and
Alantha Newman and
Lukas Vogl
STOC '24
Approximating Small Sparse Cuts (arXiv)
with
Aditya Anand and
Jason Li and
Thatchaphol Saranurak
STOC '24
Separating k-Median from the Supplier Version (arXiv)
with
Aditya Anand
IPCO '24
A PTAS for l0-Low Rank Approximation: Solving Dense CSPs over Reals (arXiv)
with
Vincent Cohen-Addad and
Chenglin Fan and
Suprovat Ghoshal and
Arnaud de Mesmay
and
Alantha Newman and
Tony Chang Wang
SODA '24
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs (arXiv)
with
Pasin Manurangsi
ITCS '24
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering (arXiv)
with Vincent Cohen-Addad and Shi Li and Alantha Newman
FOCS '23
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs (arXiv)
with Suprovat Ghoshal
FOCS '23
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median (arXiv)
with Vincent Cohen-Addad and Fabrizio Grandoni and Chris Schwiegelshohn
SODA '23
On the Fine-Grained Complexity of Approximating k-Center in Sparse Graphs (SOSA)
with Amir Abboud and Vincent Cohen-Addad and Pasin Manurangsi
SOSA '23
A Local Search-Based Approach for Set Covering (arXiv)
with Anupam Gupta and Jason Li
SOSA '23
Strong Hardness of Approximation for Tree Transversals (arXiv)
with Pengxiang Wang
Information Processing Letters (IPL) '23
Correlation Clustering with Sherali-Adams (arXiv)
with Vincent Cohen-Addad and Alantha Newman
FOCS '22
Fitting Metrics and Ultrametrics with Minimum Disagreements (arXiv)
with Vincent Cohen-Addad and Chenglin Fan and Arnaud de Mesmay
FOCS '22
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems (arXiv)
with Amir Abboud and Vincent Cohen-Addad and Pasin Manurangsi
ICALP '22
A Characterization of Approximability for Biased CSPs (arXiv)
with Suprovat Ghoshal
STOC '22
Matroid-Based TSP Rounding for Half-Integral Solutions (arXiv)
with Anupam Gupta and Jason Li and Marcin Mucha and Heather Newman and Sherry Sarkar
IPCO '22
On Some Variants of Euclidean K-Supplier (arXiv) (ORL)
with Viswanath Nagarajan and Lily Wang
Operations Research Letters
Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem (ITCS)
with Vijay Bhattiprolu and Madhur Tulsiani
ITCS '22
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p-metrics (arXiv)
with Vincent Cohen-Addad and Karthik C.S.
SODA '22
A Constant-factor Approximation for Weighted Bond Cover (arXiv)
with Eun Jung Kim and Dimitrios Thilikos
APPROX '21
A Framework for Quadratic Form Maximization over Convex Sets through Non-Convex Relaxations (STOC) (Full version)
with Vijay Bhattiprolu and Assaf Naor
STOC '21
On Approximability of Clustering Problems Without Candidate Centers (arXiv)
with Vincent Cohen-Addad and Karthik C.S.
SODA '21
The Connectivity Threshold for Dense Graphs (SODA)
with Anupam Gupta and Jason Li
SODA '21
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion (arXiv)
with Jungho Ahn and Eun Jung Kim
ISAAC 2020
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering (arXiv)
with Vaggos Chatziafratis and Neha Gupta
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms (arXiv)
with Andreas Emil Feldmann and Karthik C.S. and Pasin Manurangsi
Algorithms (Journal)
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection (arXiv)
with Sara Ahmadian and Vaggos Chatziafratis and Alessandro Epasto and Mohammad Mahdian and Konstantin Makarychev and Grigory Yaroslavtsev
AISTATS '20
The Karger-Stein Algorithm is Optimal for k-cut (arXiv)
with Anupam Gupta and Jason Li
STOC '20, invited to SICOMP special issue (regretfully declined)
Journal version: Optimal Bounds for the k-cut Problem (arXiv) (JACM) additionally with David G. Harris.
LP-branching algorithms based on biased graphs (arXiv)
with Magnus Wahlstrom
Magnus' earlier version (SODA '13).
Improved 3LIN Hardness via Linear Label Cover (ECCC)
with Devanathan Thiruvenkatachari and Subhash Khot and Prahladh Harsha
APPROX '19
Tight FPT Approximations for k-Median and k-Means (arXiv)
with Vincent Cohen-Addad and Anupam Gupta and Amit Kumar and Jason Li
ICALP '19
The Number of Minimum k-Cuts: Improving the Karger-Stein Bound (arXiv)
with Anupam Gupta and Jason Li
STOC '19
Losing Treewidth by Separating Subsets (arXiv)
with Anupam Gupta and Jason Li and Pasin Manurangsi and Michał Włodarczyk
SODA '19
A PTAS for lp-Low Rank Approximation (arXiv)
with Frank Ban and Vijay Bhattiprolu and Karl Bringmann and Pavel Kolev and David Woodruff
SODA '19
Approximating Operator Norms via Generalized Krivine Rounding (arXiv)
with Vijay Bhattiprolu and Mrinalkanti Ghosh and Venkatesan Guruswami and Madhur Tulsiani
SODA '19 (merged with below)
Inapproximability of Matrix p → q Norms (ECCC)
with Vijay Bhattiprolu and Mrinalkanti Ghosh and Venkatesan Guruswami and Madhur Tulsiani
SODA '19 (merged with above)
Faster Exact and Approximate Algorithms for k-Cut (arXiv)
with Anupam Gupta and Jason Li
FOCS '18
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities (arXiv)
with Sahil Singla
ESA '18
Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams
with Kijung Shin and Mohammad Hammoud and Jinoh Oh and Christos Faloutsos
PAKDD '18
An FPT Algorithm Beating 2-Approximation for k-Cut (arXiv)
with Anupam Gupta and Jason Li
SODA '18
Understanding the Correlation Gap for Matchings (arXiv)
with Guru Guruganesh
FSTTCS '17
Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere (ECCC)
with Vijay Bhattiprolu and Mrinalkanti Ghosh and Venkatesan Guruswami and Madhur Tulsiani
FOCS '17
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere (arXiv)
with Vijay Bhattiprolu and Venkatesan Guruswami
RANDOM '17
Global and Fixed-terminal Cuts in Digraphs (arXiv)
with Kristóf Bérczi and Karthekeyan Chandrasekaran and Tamás Király and Chao Xu
APPROX '17
Journal version (algorithms): Beating the 2-approximation factor for global bicut. Mathematical Programming Series A
Why You Should Charge Your Friends for Borrowing Your Stuff
with Kijung Shin and Dhivya Eswaran and Ariel Procaccia
IJCAI '17
Featured in New Scientist
Improved Hardness for Cut, Interdiction, and Firefighter Problems (arXiv)
ICALP '17
Best Student Paper
APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items (arXiv) (IPL)
Information Processing Letters (IPL) '17
Improved and Simplified Inapproximability for k-means (arXiv) (IPL)
with Melanie Schmidt and John Wright
Information Processing Letters (IPL) '17
Minimum Birkhoff-von Neumann Decomposition (PDF)
with Janardhan Kulkarni and Mohit Singh
IPCO '17
Maximum Matching in the Online Batch-Arrival Model (PDF)
with Sahil Singla
IPCO '17
Partitioning a Graph into Small Pieces with Applications to Path Transversal (arXiv)
SODA '17
Journal version: Mathematical Programming Series A
Simple Proof of Hardness of Feedback Vertex Set (TOC)
with Venkatesan Guruswami
Theory of Computing (TOC) '16 (Note)
Nearly Optimal NP-hardness of Unique Coverage (ECCC)
with Venkatesan Guruswami
SODA '16
Journal version: SIAM Journal on Computing (SICOMP)
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises (arXiv)
with Vijay Bhattiprolu and Venkatesan Guruswami
APPROX '15
Towards a Characterization of Approximation Resistance for Symmetric CSPs (ECCC)
with Venkatesan Guruswami
APPROX '15
Journal version: Theory of Computing (ToC) (Invited)
Inapproximability of H-Transversal/Packing (arXiv)
with Venkatesan Guruswami
APPROX '15
Journal version: To appear in SIAM Journal on Discrete Mathematics (SIDMA)
Earlier version: Inapproximability of Feedback Vertex Set for Bounded Length Cycles (ECCC)
Hardness of Graph Pricing Through Generalized Max-Dicut (arXiv)
STOC '15
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs (ECCC)
with Venkatesan Guruswami
SODA '15
Journal version: Combinatorica
LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes (arXiv)
with Badih Ghazi
SODA '15
Journal version: IEEE Transactions on Information Theory (IEEE)
Complexity of Approximating CSP with Balance/Hard Constraints (ECCC)
with Venkatesan Guruswami
ITCS '14
Journal version: Theory of Computing Systems (ToCS)
Improved Bounds on the Price of Stability in Network Cost Sharing Games (PDF)
with Katrina Ligett
EC '13
Clustering Affine Subspaces: Hardness and Algorithms (PDF)
with Leonard Schulman
SODA '13
Progress on Pricing with Peering (PDF)
with David Buchfuhrer, Lachlan Andrew, Ao Tang, and Steven Low
CISS '08
Pricing in the Presence of Peering (PDF)
with David Buchfuhrer, Lachlan Andrew, Ao Tang, and Steven Low
Allerton '07