10 citations · 10 across the 4 of their papers we have counts for
4 papers
Improved Hardness for Cut, Interdiction, and Firefighter Problems
Euiwoong Lee
We study variants of the classic - cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). - For any constant and…
Partitioning a Graph into Small Pieces with Applications to Path Transversal
Euiwoong Lee
Given a graph and an integer , we study -Vertex Seperator (resp. -Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) su…
LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes
Badih Ghazi, Euiwoong Lee
Random (dv,dc)-regular LDPC codes are well-known to achieve the Shannon capacity of the binary symmetric channel (for sufficiently large dv and dc) under exponential time decoding.…
Hardness of Graph Pricing through Generalized Max-Dicut
Euiwoong Lee
The Graph Pricing problem is among the fundamental problems whose approximability is not well-understood. While there is a simple combinatorial 1/4-approximation algorithm, the bes…