Andreev's Problem asks the following: Given an integer d and a subset of S F q F q , is there a polynomial y = p ( x ) of degree at most d such that for every a F q , ( a p ( a )) S ? We show an AC 0 [ ] lower bound for this problem.

This problem appears to be similar to the list recovery problem for degree d -Reed-Solomon codes over F q which asks the following: Given subsets A 1 A q of F q , output all (if any) Reed-Solomon codewords contained in A 1 A q . For our purpose, we study this problem when A 1 A q are random subsets of a given size, which may be of independent interest.