Past Events

PhD Defense Combinatorial problems in algorithms and complexity theory
× Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close 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 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 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 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(q),O(1))-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.

: