My Photo

Euiwoong Lee

Contact

Address:
408 Warren Weaver Hall
Courant Institute of Mathematical Sciences
New York University

Email: (my first name that has 8 letters) at cims dot nyu dot edu


I am a postdoc at New York University hosted by Oded Regev and Subhash Khot, as part of the Simons Collaboration on Algorithms and Geometry. I was a research fellow at Simons Institute for the Theory of Computing, participating the Bridging Continuous and Discrete Optimization program. I received my PhD from Carnegie Mellon University, where I was fortunate to be 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.


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


Publications

Losing Treewidth by Separating Subsets (arXiv)
with Anupam Gupta and Jason Li and Pasin Manurangsi and Michał Włodarczyk

A PTAS for lp-Low Rank Approximation (arXiv)
with Frank Ban and Vijay Bhattiprolu and Karl Bringmann and Pavel Kolev and David Woodruff

Approximating Operator Norms via Generalized Krivine Rounding (arXiv)
with Vijay Bhattiprolu and Mrinalkanti Ghosh and Venkatesan Guruswami and Madhur Tulsiani

Inapproximability of Matrix p → q Norms (ECCC)
with Vijay Bhattiprolu and Mrinalkanti Ghosh and Venkatesan Guruswami and Madhur Tulsiani



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

Here is my CV.