Constructing Covering Codes
Luca Teodoro Filippini · Repository for Publications and Research Data (ETH Zurich) · 2016
Given r, n ∈ N, the problem of constructing a set C ⊆ {0, 1} n such that every element in {0, 1} n has Hamming distance at most r from some element in C is called the covering code construction problem.Constructing a covering code of minimal size is such a hard task that even for r = 1, n = 10 we don't know the exact size of the minimal code.Therefore, approximations are often studied and employed.Among the several applications that such a construction has, it plays a key role in one of the fastest 3-SAT algorithms known to date.The main contribution of this thesis is presenting a Las Vegas algorithm for constructing a covering code with linear radius, derived from the famous Monte Carlo algorithm of random codeword sampling.Our algorithm is faster than the deterministic algorithm presented in [5] by a cubic root factor of the polynomials involved.We furthermore study the problem of determining the covering radius of a code: it was already proven N P-complete for r = n/2, and we extend the proof to a wider range of radii.Along the way, we introduce a new Satisfiability problem, and investigate its hardness.i Acknowledgements Foremost, I would like to thank my advisor Prof. Welzl for having stimulated my interest in the field of combinatorial algorithms during the SAT course, for a great deal of notation borrowed from the course book [19], and for the possibility of writing this thesis under his supervision.I also thank my co-advisor Chidambaram for his suggestions and for proof-reading the thesis.Furthermore, my gratitude goes to my fellow students in the Theoretical Computer Science track for continuous support throughout my studies, and in particular, to my dear friend Miloš, for his unlimited curiosity in this field.For precious coffee breaks and an everlasting billiards rivalry I have to thank my friends Gabriele, Billy, Kevin and Radek.I also thank my parents Angela and Rocco and my second mother Lilia, for supporting me in every sense, during my studies.Last, but not least, I am grateful to my beloved fiancée