Aditya Potukuchi

activity

20152026

most citedDiscrepancy in random hypergraph models

8 citations · 13 across the 14 of their papers we have counts for

collaborators

Showing 2019Show all

4 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$ …

math.CO2019

A spectral bound on hypergraph discrepancy

Aditya Potukuchi

Let $H$ be a $t$ -regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m \times n$ incidence matrix of $H$ and let us denote $λ=\max_{v \perp \overl…

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.IT2019

Improved efficiency for covering codes matching the sphere-covering bound

Aditya Potukuchi, Yihan Zhang

A covering code is a subset $C \subseteq {0, 1}^{n}$ with the property that any $z \in {0, 1}^{n}$ is close to some $c \in C$ in Hamming distance. For every $ε,δ>…

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

A spectral bound on hypergraph discrepancy

Simplified inpproximability of hypergraph coloring via t-agreeing families

Improved efficiency for covering codes matching the sphere-covering bound

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