Generátory pseudonáhodností pro polynomy - Pseudorandom generators for polynomials - Wikipedia

v teoretická informatika, a pseudonáhodný generátor pro polynomy nízkého stupně je efektivní postup, který mapuje krátké skutečně náhodné semeno na delší pseudonáhodný řetězec takovým způsobem, že polynomy nízkého stupně nemohou rozlišit výstupní distribuci generátoru od skutečně náhodného rozdělení. To znamená, že vyhodnocení libovolného polynomu nízkého stupně v bodě určeném pseudonáhodným řetězcem je statisticky blízké vyhodnocení stejného polynomu v bodě, který je náhodně vybrán rovnoměrně.

Generátory pseudonáhodností pro polynomy nízkého stupně jsou konkrétním příkladem pseudonáhodné generátory pro statistické testy, kde se za statistické testy považují hodnocení polynomů nízkého stupně.

Definice

Generátor pseudonáhod ${ displaystyle G: mathbb {F} ^ { ell} rightarrow mathbb {F} ^ {n}}$ pro polynomy stupně ${ displaystyle d}$ přes konečné pole ${ displaystyle mathbb {F}}$ je efektivní postup, který mapuje posloupnost ${ displaystyle ell}$ prvky pole na posloupnost ${ displaystyle n}$ prvky pole takové, že všechny ${ displaystyle n}$-měnit polynom nad ${ displaystyle mathbb {F}}$ stupně ${ displaystyle d}$ je oklamán distribucí výstupu ${ displaystyle G}$Jinými slovy, pro každý takový polynom ${ displaystyle p (x_ {1}, tečky, x_ {n})}$, statistická vzdálenost mezi distribucemi ${ displaystyle p (U_ {n})}$ a ${ displaystyle p (G (U _ { ell}))}$ je nanejvýš malý ${ displaystyle epsilon}$, kde ${ displaystyle U_ {k}}$ je rovnoměrné rozdělení ${ displaystyle mathbb {F} ^ {k}}$.

Konstrukce

Lovett (3. zleva) v roce 2009

Pouzdro ${ displaystyle d = 1}$ odpovídá pseudonáhodné generátory pro lineární funkce a je vyřešen generátory s malým zkreslením Například výstavba Naor a Naor (1990) dosahuje délky semen ${ displaystyle ell = log n + O ( log ( epsilon ^ {- 1}))}$, což je optimální až do stálých faktorů.

Bogdanov & Viola (2007) domníval se, že součet generátorů s malým zkreslením ošálí polynomy nízkého stupně a dokázali to dokázat podle Gowersova inverzní domněnka.Lovett (2009) se bezpodmínečně prokázalo, že součet ${ displaystyle 2 ^ {d}}$ prostory s malým zkreslením ošálí polynomy stupně ${ displaystyle d}$.Viola (2008) dokazuje, že ve skutečnosti, přičemž součet pouze ${ displaystyle d}$ generátory s malým zkreslením stačí k oklamání polynomů stupně ${ displaystyle d}$Analýza Viola (2008) dává délku semene ${ displaystyle ell = d cdot log n + O (2 ^ {d} cdot log ( epsilon ^ {- 1}))}$.

Reference

• Bogdanov, Andrej; Viola, Emanuele (2007), "Pseudonáhodné bity pro polynomy", Sborník ze 48. výročního symposia o základech informatiky (FOCS 2007): 41–51, doi:10.1109 / FOCS.2007.56, ISBN  978-0-7695-3010-9CS1 maint: ref = harv (odkaz)
• Lovett, Shachar (2009), „Bezpodmínečné pseudonáhodné generátory pro polynomy nízkého stupně“, Teorie výpočtu, 5 (3): 69–82, doi:10.4086 / toc.2009.v005a003CS1 maint: ref = harv (odkaz)
• Naor, Joseph; Naor, Moni (1990), „Pravděpodobnostní prostory s malou odchylkou: efektivní konstrukce a aplikace“, Proceedings of the 22. Annual ACM Symposium on Theory of Computing, STOC 1990: 213–223, CiteSeerX  10.1.1.421.2784, doi:10.1145/100216.100244, ISBN  978-0897913614CS1 maint: ref = harv (odkaz)
• Viola, Emanuele (2008), "Součet d generátorů malých zkreslení ošálí polynomy stupně d" (PDF), Sborník 23. výroční konference o výpočetní složitosti (CCC 2008): 124–127, CiteSeerX  10.1.1.220.1554, doi:10.1109 / CCC.2008.16, ISBN  978-0-7695-3169-4CS1 maint: ref = harv (odkaz)