On the $text{AC}^0[oplus]$ complexity of Andreevs Problem

Andreevs 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,ldots,A_q$ of $mathbb{F}_q$, output all (if any) the Reed-Solomon codewords contained in $A_1times cdots times A_q$. For our purpose, we study this problem when $A_1, ldots, A_q$ are random subsets of a given size, which may be of independent interest.