All reports by Author Aditya Potukuchi:

__
TR20-070
| 4th May 2020
__

Ben Lund, Aditya Potukuchi#### On the list recoverability of randomly punctured codes

Revisions: 1

__
TR19-096
| 23rd July 2019
__

Aditya Potukuchi#### On the $\text{AC}^0[\oplus]$ complexity of Andreev's Problem

__
TR19-048
| 2nd April 2019
__

Per Austrin, Amey Bhangale, Aditya Potukuchi#### Simplified inpproximability of hypergraph coloring via t-agreeing families

Ben Lund, Aditya Potukuchi

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound.

In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound.

It was previously known that there are Reed-Solomon codes that do not have this ...
more >>>

Aditya Potukuchi

Andreev's Problem asks the following: Given an integer $d$ and a subset of $S \subseteq \mathbb{F}_q \times \mathbb{F}_q$, is there a polynomial $y = p(x)$ of degree at most $d$ such that for every $a \in \mathbb{F}_q$, $(a,p(a)) \in S$? We show an $\text{AC}^0[\oplus]$ lower bound for this problem.

... more >>>Per Austrin, Amey Bhangale, Aditya Potukuchi

We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal $t$-agreeing families of $[q]^n$. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs ... more >>>