Janurary 20, 2016
First Speaker:
Euiwoong Lee
Nearly Optimal NP-Hardness of Unique Coverage
The Unique Coverage problem, given a universe V of elements and a collection E of subsets of V, asks to find $S \subseteq V$ to maximize the number of e in E that intersects S in exactly one element. When each e has cardinality at most k, it is also known as 1-in-k Hitting Se}, and admits a simple Omega(1 / log k)-approximation algorithm.
For constant k, we prove that 1-in-k Hitting Set is NP-hard to approximate within a factor O(1 / log k). This improves the result of Guruswami and Zhou [SODA'11, ToC'12], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor O(1 / log^{1 - epsilon} n) for any epsilon > 0, unless NP admits quasipolynomial time algorithms. This improves the results of Demaine et al. [SODA'06, SICOMP'08], including their O(1 / log^{1/3} n) inapproximability factor which was proven under the Random 3SAT Hypothesis.
Our simple proof combines ideas from two classical inapproximability results for Set Cover and Constraint Satisfaction Problem, made efficient by various derandomization methods based on bounded independence.
Based on joint work with Venkatesan Guruswami.
BIO:
Euiwoong Lee is a PhD student at Carnegie Mellon University, advised by Venkat Guruswami. Before coming to CMU, he obtained B.S. and M.S. from Caltech. His research interests include approximation algorithms and hardness of approximation for optimization problems.
Second Speaker:
Joshua Brakensiek
Efficient Low-Redundancy Codes for Correcting Multiple Deletions
We consider the problem of constructing binary codes to recover from k--bit deletions with efficient encoding/decoding, for a fixed k. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with \approx 2^n/n codewords of length n, i.e., at most log(n) bits of redundancy. However, even for the case of two deletions, there was no known explicit construction with redundancy less than n^\Omega(1).
For any fixed k, we construct a binary code with c_k log(n) redundancy that can be decoded from k deletions in O_k(n log^4(n)) time. The coefficient c_k can be taken to be O(k^2 log(k)), which is only quadratically worse than the optimal, non-constructive bound of O(k). We also indicate how to modify this code to allow for a combination of up to k insertions and deletions.
We also note that among linear codes capable of correcting k deletions, the (k+1)-fold repetition code is essentially the best possible.
Based on joint work with Venkatesan Guruswami and Samuel Zbarsky
BIO:
Joshua Brakensiek is an undergraduate in the Department of Mathematical Sciences at Carnegie Mellon University. He has conducted research in topics such as coding theory, hardness of approximation, and computational astrophysics.
