CS Events Monthly View
PhD DefenseCombinatorial problems in algorithms and complexity theory 


Wednesday, March 25, 2020, 12:30pm  01:30pm 

Speaker: Aditya Potukuchi
Location : Remote via Webex
Committee:
Swastik Kopparty (chair), Jeff Kahn, Shubhangi Saraf, Raghu Meka (external)
Event Type: PhD Defense
Abstract: Theoretical Computer Science has had 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 ReedMuller code of rate 1  Theta((\log^r n)/n) can be recovered from o((log^((r1)/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 NPhard to properly 2color a kuniform (k  O(sqrt{k}))rainbow colorable hypergraph. In particular, we show that it is NPhard to properly 2color a 4uniform $3$rainbow colorable hypergraph. We further extend this using a notion of almost rainbow colorability. We show that given a kuniform hypergraph where there is a $(k  \sqrt{ck})$coloring of the vertices such that every edge gets (k  3sqrt{ck})colors, it is NPhard to properly ccolor it. Among the techniques are topological methods to lower bound the chromatic number of certain hypergrpahs, 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 tregular 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 tregular 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 qary 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(q),O(1))zeroerror listdecodable. In particular, this shows that there are ReedSolomon codes that are zeroerror listrecoverable beyond the Johnson radius. This immediately improves the degree bound for unbalanced expanders obtained from randomly punctured ReedSolomon codes.
: