10 citations · 12 across the 12 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2016★ 10 cited
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…
cs.CC2014
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.…