Pseudoslumpgeneratorer för polynom

Inom teoretisk datavetenskap är en pseudoslumpgenerator för låggradiga polynom en effektiv procedur som mappar ett kort verkligt slumpmässigt frö till en längre pseudoslumpmässig sträng på ett sådant sätt att låggradiga polynom inte kan skilja generatorns utmatningsfördelning från den verkligt slumpmässiga strängen. distribution. Det vill säga att utvärdera ett låggradigt polynom vid en punkt som bestäms av den pseudoslumpmässiga strängen är statistiskt nära att utvärdera samma polynom vid en punkt som väljs enhetligt slumpmässigt.

Pseudoslumpgeneratorer för låggradiga polynom är ett särskilt exempel på pseudoslumpgeneratorer för statistiska test, där de statistiska testerna som beaktas är utvärderingar av låggradiga polynom.

Definition

En pseudoslumpgenerator $G:\mathbb {F} ^{\ell }\rightarrow \mathbb {F} ^{n}$ för polynom av grad $d$ över en ändlig fält $\mathbb {F}$ är en effektiv procedur som mappar en sekvens av $\ell$ fältelement till en sekvens av $n$ fältelement så att alla $n$ -variatpolynom över $\mathbb {F}$ av graden $d$ luras av utdatafördelningen av $G$ . Med andra ord, för varje sådant polynom $p(x_{1},\dots ,x_{n})$ , det statistiska avståndet mellan fördelningarna ${ \displaystyle p(U_{n})}$ och $p(G(U_{\ell }))$ är högst ett litet $\epsilon$ , där $U_{k}$ är den enhetliga fördelningen över $\mathbb {F} ^{k}$ .

Konstruktion

Lovett (3:e från vänster) 2009

Fallet $d=1$ motsvarar pseudoslumpgeneratorer för linjära funktioner och löses av småförspänningsgeneratorer . Till exempel uppnår konstruktionen av Naor & Naor (1990) en frölängd på $\ell =\log n+O(\log(\epsilon ^{-1}))$ , vilket är optimalt upp till konstanta faktorer.

Bogdanov & Viola (2007) antog att summan av småförspänningsgeneratorer lurar låggradiga polynom och kunde bevisa detta under Gowers omvända gissning. Lovett (2009) bevisade villkorslöst att summan av $2^{d}$ små bias mellanslag lurar polynom av graden $d$ . Viola (2008) bevisar att det i själva verket är tillräckligt att ta summan av $d$ små biasgeneratorer för att lura polynom med graden $d$ . Analysen av Viola (2008) ger en frölängd på $\ell =d\cdot \log n+O(2^ {d}\cdot \log(\epsilon ^{-1}))$ .

•    Bogdanov, Andrej; Viola, Emanuele (2007), "Pseudorandom Bits for Polynomials" , Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS 2007) : 41–51, doi : 10.1109/FOCS.2007.596 , 5-301-707 , 5-301 -9 , S2CID 1142549
• Lovett, Shachar (2009), "Unconditional Pseudorandom Generators for Low Degree Polynomials", Theory of Computing , 5 (3): 69–82, doi : 10.4086/toc.2009.v005a003
•     Naor, Joseph; Naor, Moni (1990), " Small-bias Probability Spaces: efficient constructions and Applications" , Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC 1990 : 213–223, CiteSeerX 10.1.1.421,017 ,017 ,017 , 017 . 100216.100244 , ISBN 978-0897913614 , S2CID 14031194
•    Viola, Emanuele (2008), "Summan av d småförspänningsgeneratorer lurar polynom av grad d" (PDF) , Proceedings of the 23rd Annual Conference on Computational Complexity (CCC 2008) : 124–127, CiteSeerX 10.1.1.5420 , doi : 10.1109/CCC.2008.16 , ISBN 978-0-7695-3169-4