Text

theses

Theoretical Computer Science has connections to several areas of mathematics and one of the more prominent of these connections is to combinatorics. Indeed, many problems in this subject are often very combinatorial in nature. These problems have either used existing techniques from combinatorics or have given rise to new combinatorial techniques. This dissertation is a collection of the study of some such problems.

1. We recover a result by Abbe, Shpilka and Wigderson which states that a Reed-Muller code of rate 1 - Theta((log^r n)/n) can be recovered from o((log^((r-1)/2))/n) randomly chosen errors in a stronger way. Namely, we show that the set of corrupted locations in the message can be recovered just from the syndrome of the message. Among the techniques are the study of tensor decomposition over finite fields and an algorithm to find the roots of a space of low degree polynomials.

2. We show that it is NP-hard to properly 2-color a k-uniform (k - O(sqrt{k}))-rainbow colorable hypergraph. In particular, we show that it is NP-hard to properly 2-color a 4-uniform $3$-rainbow colorable hypergraph. We further extend this using a notion of almost rainbow colorability. We show that given a k-uniform hypergraph where there is a $(k - sqrt{ck})$-coloring of the vertices such that every edge gets (k - 3sqrt{ck})-colors, it is NP-hard to properly c-color it. Among the techniques are topological methods to lower bound the chromatic number of certain hypergraphs and a theorem of Sarkaria on the chromatic number of the generalized Kneser hypergraph.

3. We show that the discrepancy of a regular hypergraph can be bounded in terms of its spectral information. Let H subset 2^{[n]} be a t-regular hypergraph where |H| >= n, and M be the |H| x n incidence matrix. Define $ lambda : = max_{v perp 1}||Mv||/||v||$. We show that the discrepancy of H is at most O(sqrt{t} + lambda). In particular, this shows that for every t, the discrepancy of a random t-regular hypergraph on m > = n hyperedges has discrepancy O(sqrt{t}) with high probability as n grows. This bound also comes with an efficient algorithm that takes $mathcal{H}$ as input and outputs a coloring that has the guaranteed discrepancy.

4. We show that every q-ary error-correcting code of distance 1 - q^{-1} - epsilon^2 can be punctured to rate tilde{Omega}((epsilon)/(log q)) so that it is (O_{rho,delta}(q),delta,rho)-zero-error list-decodable. In particular, this shows that there are Reed-Solomon codes that are zero-error list-recoverable beyond the Johnson radius. This immediately improves the degree bound for unbalanced expanders obtained from randomly punctured Reed-Solomon codes

ETD_10919

Ph.D.

Includes bibliographical references

doi:10.7282/t3-kz39-ec82

ETD doctoral

The author owns the copyright to this work.