摘要：Andreev's Problem is the following: Given an integer d and a subset of S subset F_q x F_q, is there a polynomial y = p(x) of degree at most d such that for every a in F_q, (a,p(a)) in S? We show an 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 F_q which states the following: Given subsets A_1,...,A_q of F_q, output all (if any) the Reed-Solomon codewords contained in A_1 x *s x A_q. In particular, we study this problem when the lists A_1, ..., A_q are randomly chosen, and are of a certain size. This may be of independent interest.
