Abstract-Vi konstruerar pseudorandom generatorer som lurar funktioner av halvrymder (tröskelfunktioner) under en mycket bred klass av produktdistributioner. Denna klass omfattar inte bara välkända fall som den enhetliga fördelningen på den diskreta kuben, den enhetliga fördelningen på den fasta kuben och den multivariata Gaussiska fördelningen, utan omfattar även alla produkter av diskreta distributioner med sannolikheter som begränsas bort från 0. Vårt första huvudresultat visar att en nyligen genomförd pseudorandom generator konstruktion av Meka och Zuckerman [19], när lämpligt modifierad, kan lura godtyckliga funktioner d halvrymder under produktdistributioner där varje koordinat har avgränsat fjärde ögonblicket. Till ε-fool alla storlekar, djupd beslut träd av halvrymder, vår pseudorandom generator använder utsädeslängd O((d log(ds/ε) + log n)·log(ds/ε)). För monotona funktioner för d-halvrymder kan utsädets längd förbättras till O((d log(d/ε) + log n) · log(d/ε)). Vi får bättre gränser för större ε; till exempel till 1/polylog(n)-fool alla monotona funktioner (log n) / log n halvrymder, vår generator kräver ett frö av längd bara O(log n). Vårt andra huvudsakliga resultat generaliserar arbetet av Diakonikolas et al. [5] för att visa att begränsat oberoende räcker för att lura funktioner i halvrymder under produktdistributioner. Om varje koordinat uppfyller ett visst starkare moment, visar vi att varje funktion som kan beräknas av en storlek-s, djup-d beslut träd av halvrymder är ε-snubbad av Õ(d 4 s 2 /ε 2 )-vis självständighet. Våra tekniska bidrag inkluderar: en ny flerdimensionell version av den klassiska Berry-Esseen theorem; en derandomization därav; en generalisering av Servedio [28] regelbundenhet lemma för halvrymder som fungerar under någon produktdistribution med avgränsade fjärde ögonblick; en utvidgning av denna regelbundenhet lemma till funktioner i många halvrymder; och, ny analys av smörgås polynomials teknik Bazzi [1] för godtyckliga produktdistributioner.
Gopalan m.fl. REF gav en generator lura halvrymder under produktdistributioner med avgränsade fjärde ögonblick, vars utsäde längd är O(log(n/ε) log(1/ε)).
Fooling Functions of Halfspaces under Product Distributions
{'venue': '2010 IEEE 25th Annual Conference on Computational Complexity', 'journal': '2010 IEEE 25th Annual Conference on Computational Complexity', 'mag_field_of_study': ['Mathematics', 'Computer Science']}