My Photo

Euiwoong Lee


7503 Gates Hillman Center
Computer Science Department
Carnegie Mellon University

Email: euiwoonl at cs dot cmu dot edu

I am a PhD student at the Computer Science Department at Carnegie Mellon University. I am fortunate to be advised by Venkatesan Guruswami. I am supported by Samsung Scholarship and Simons Award for Graduate Students in TCS.

Interests and Current Research
Approximation Algorithms
Hardness of Approximation
Convex Hierarchies (e.g., Sum of Squares, Sherali-Adams)

Improved Hardness for Cut, Interdiction, and Firefighter Problems (arXiv)

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere (ECCC)
with Vijay Bhattiprolu and Mrinalkanti Ghosh and Venkatesan Guruswami and Madhur Tulsiani
Earlier version: Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy (arXiv)

Global and Fixed-terminal Cuts in Digraphs (arXiv)
with Kristóf Bérczi and Karthekeyan Chandrasekaran and Tamás Király and Chao Xu

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

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

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises (arXiv)
with Vijay Bhattiprolu and Venkatesan Guruswami

Towards a Characterization of Approximation Resistance for Symmetric CSPs (ECCC)
with Venkatesan Guruswami
Journal version: To appear in Theory of Computing (Invited)

Inapproximability of H-Transversal/Packing (arXiv)
with Venkatesan Guruswami
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: To appear in Combinatorica

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes (arXiv)
with Badih Ghazi
SODA '15
Journal version: To appear in IEEE Transactions on Information Theory

Complexity of Approximating CSP with Balance/Hard Constraints (ECCC) (TOCS)
with Venkatesan Guruswami
ITCS '14
Journal version: Theory of Computing Systems (TOCS) '16

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

Here is my CV.