2026-07-23T08:16:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11587 2024-03-06T10:48:23Z ddc:004 open_access

On the AC^0[oplus] Complexity of Andreev’s Problem Potukuchi, Aditya List Recovery Sharp Threshold Fourier Analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Potukuchi 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.25 urn:nbn:de:0030-drops-115879 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.25 eng https://creativecommons.org/licenses/by/3.0/legalcode