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

Abstract

Andreev's Problem states 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. This problem appears to be similar to the list recovery problem for degree $d$-Reed-Solomon codes over ${\mathbb{F}}_q$ which states the following: Given subsets $A_1,\dots ,A_q$ of ${\mathbb{F}}_q$, output all (if any) the Reed-Solomon codewords contained in $A_1\times \cdots \times A_q$. For our purpose, we study this problem when $A_1,\dots ,A_q$ are random subsets of a given size, which may be of independent interest.

20 pages