14 citations · 51 across the 29 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
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.…
cs.DS2014
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…