Aditya Potukuchi

activity

20172021

most citedOn the list recoverability of randomly punctured codes

4 citations · 4 across the 5 of their papers we have counts for

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2019

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

Aditya Potukuchi

Andreev's Problem states the following: Given an integer $d$ and a subset of $S \subseteq F_{q} \times F_{q}$ , is there a polynomial $y = p (x)$ of degree at most $d$ …

cs.CC2019

Simplified inpproximability of hypergraph coloring via t-agreeing families

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}$ . Sp…

cs.CC2018

Improved Inapproximability of Rainbow Coloring

Per Austrin, Amey Bhangale, Aditya Potukuchi

A rainbow $q$ -coloring of a $k$ -uniform hypergraph is a $q$ -coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2\lflo…

On the AC0[⊕] complexity of Andreev's Problem

Simplified inpproximability of hypergraph coloring via t-agreeing families

Improved Inapproximability of Rainbow Coloring

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