×

More on bounded independence plus noise: pseudorandom generators for read-once polynomials. (English) Zbl 1462.68034

Summary: We construct pseudorandom generators with improved seed length for several classes of tests. First, we consider the class of read-once polynomials over GF(2) in \(m\) variables. For error \(\varepsilon\) we obtain seed length \(\tilde O(\log(m/\varepsilon)\log(1/\varepsilon))\). This is optimal up to a factor of \(\log(1/\varepsilon)\cdot \operatorname{poly}\log\log(m/\varepsilon)\). The previous best seed length was polylogarithmic in \(m\) and \(1/\varepsilon \).
Second, we consider product tests \(f: \{0,1\}^m \to \mathbb{C}_{\le 1}\). These tests are the product of \(k\) functions \(f_i: \{0,1\}^\ell\to\mathbb{C}_{\le 1}\), where the inputs of the \(f_i\) are disjoint subsets of the \(m\) variables and \(\mathbb{C}_{\le 1}\) is the complex unit disk. Here we obtain seed length \(\ell \cdot \operatorname{polylog} (m/\varepsilon)\). This implies better generators for other classes of tests. If moreover the \(f_i\) have output range \(\{-1, 0, 1\}\) then we obtain seed length \(\tilde O((\log(k/\varepsilon) + \ell) (\log(1/\varepsilon) + \log\log m))\). This is again optimal up to a factor of \(\log(1/\varepsilon) \cdot \operatorname{polylog}(\ell, \log k, \log m, \log(1/\varepsilon))\), while the previous best seed length was \(\ge \sqrt k\).
A main component of our proofs is showing that these classes of tests are fooled by almost \(d\)-wise independent distributions perturbed with noise.

MSC:

68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
11K45 Pseudo-random numbers; Monte Carlo methods
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [1] MIKLÓSAJTAI, JÁNOSKOMLÓS,ANDENDRESZEMERÉDI: Deterministic simulation in LOGSPACE. InProc. 19th STOC, pp. 132-140. ACM Press, 1987. [doi:10.1145/28395.28410]3
[2] [2] MIKLÓSAJTAI ANDAVIWIGDERSON: Deterministic simulation of probabilistic constant depth circuits.Advances in Computing Research, 5(1):199-222, 1989. Preliminary version inFOCS’85.4
[3] [3] ROYARMONI, MICHAELSAKS, AVIWIGDERSON,ANDSHIYUZHOU: Discrepancy sets and pseudorandom generators for combinatorial rectangles. InProc. 37th FOCS, pp. 412-421. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548500]3
[4] [4] LOUAYM. J. BAZZI: Polylogarithmic independence can fool DNF formulas.SIAM J. Comput., 38(6):2220-2272, 2009. Preliminary version inFOCS’07. [doi:10.1137/070691954]35 · Zbl 1188.68156
[5] [5] ANDREJBOGDANOV, PERIKLISA. PAPAKONSTANTINOU,ANDANDREWWAN: Pseudorandomness for read-once formulas. InProc. 52nd FOCS, pp. 240-246. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.57]3 · Zbl 1292.68110
[6] [6] ANDREJBOGDANOV ANDEMANUELEVIOLA: Pseudorandom bits for polynomials.SIAM J. Comput., 39(6):2464-2486, 2010. Preliminary version inFOCS’07. [doi:10.1137/070712109]2 · Zbl 1211.68215
[7] [7] RAVIBOPPANA, JOHANHÅSTAD, CHINHOLEE,ANDEMANUELEVIOLA: Bounded independence versus symmetric tests.ACM Trans. Computation Theory, 11(4):21:1-27, 2019. Preliminary version inRANDOM’16. [doi:10.1145/3337783]9 · Zbl 1495.68151
[8] [8] SURESHCHARI, PANKAJROHATGI,ANDARAVINDSRINIVASAN: Improved algorithms via approximations of probability distributions.J. Comput. System Sci., 61(1):81-107, 2000. Preliminary version inSTOC’94. [doi:10.1006/jcss.1999.1695]4,6 · Zbl 0960.68172
[9] [9] ESHANCHATTOPADHYAY, POOYAHATAMI, OMERREINGOLD,ANDAVISHAYTAL: Improved pseudorandomness for unordered branching programs through local monotonicity. InProc. 50th STOC, pp. 363-375. ACM Press, 2018. [doi:10.1145/3188745.3188800]3 · Zbl 1427.68058
[10] [10] ANINDYADE: Beyond the central limit theorem: asymptotic expansions and pseudorandomness for combinatorial sums. InProc. 56th FOCS, pp. 883-902. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.59]3
[11] [11] ANINDYADE, OMIDETESAMI, LUCATREVISAN,ANDMADHURTULSIANI: Improved pseudorandom generators for depth 2 circuits. InProc. 14th Internat. Workshop on Randomization and
[12] [12] GUYEVEN, ODEDGOLDREICH, MICHAELLUBY, NOAMNISAN,ANDBOBANVELI ˇCKOVI ´C: Efficient approximation of product distributions.Random Structures Algorithms, 13(1):1-16, · Zbl 0959.68553
[13] [13] MICHAELA. FORBES ANDZANDERKELLEY: Pseudorandom generators for read-once branching programs, in any order. InProc. 59th FOCS, pp. 946-955. IEEE Comp. Soc. Press, 2018. [doi:10.1109/FOCS.2018.00093,arXiv:1808.06265]9,40,41
[14] [14] DMITRYGAVINSKY, SHACHARLOVETT,ANDSRIKANTHSRINIVASAN: Pseudorandom generators for read-once ACC0. InProc. 27th IEEE Conf. on Computational Complexity (CCC’12), pp. 287-297. IEEE Comp. Soc. Press, 2012. [doi:10.1109/CCC.2012.37]2,7
[15] [15] PARIKSHITGOPALAN, DANIELM. KANE,ANDRAGHUMEKA: Pseudorandomness via the discrete Fourier transform.SIAM J. Comput., 47(6):2451-2487, 2018. Preliminary version in FOCS’15. [doi:10.1137/16M1062132,arXiv:1506.04350]3,7,18,46 · Zbl 1410.65007
[16] [16] PARIKSHITGOPALAN, RAGHUMEKA, OMERREINGOLD, LUCATREVISAN,ANDSALILVADHAN: Better pseudorandom generators from milder pseudorandom restrictions. InProc. 53rd FOCS, pp. 120-129. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.77]3,4,6,7,8,33,35
[17] [17] PARIKSHITGOPALAN, RAGHUMEKA, OMERREINGOLD,ANDDAVIDZUCKERMAN: Pseudorandom generators for combinatorial shapes.SIAM J. Comput., 42(3):1051-1076, 2013. Preliminary version inSTOC’11. [doi:10.1137/110854990]3,6 · Zbl 1275.68078
[18] [18] PARIKSHITGOPALAN, RYANO’DONNELL, YIWU,ANDDAVIDZUCKERMAN: Fooling functions of halfspaces under product distributions. InProc. 25th IEEE Conf. on Computational
[19] [19] PARIKSHITGOPALAN ANDAMIRYEHUDAYOFF: Inequalities and tail bounds for elementary symmetric polynomial with applications, 2014. [arXiv:1402.3543]3,6,7
[20] [20] ELADHARAMATY, CHINHOLEE,ANDEMANUELEVIOLA: Bounded independence plus noise fools products.SIAM J. Comput., 47(2):493-523, 2018. Preliminary version inCCC’17. [doi:10.1137/17M1129088]3,4,5,9,33,41 · Zbl 1441.94114
[21] [21] HAMEDHATAMI: Lecture notes on Harmonic Analysis of Boolean functions, 2014. Available at author’s home page.33
[22] [22] RUSSELLIMPAGLIAZZO, NOAMNISAN,ANDAVIWIGDERSON: Pseudorandomness for network algorithms. InProc. 26th STOC, pp. 356-364. ACM Press, 1994. [doi:10.1145/195058.195190]3 · Zbl 1345.68269
[23] [23] CHINHOLEE: Fourier bounds and pseudorandom generators for product tests. In34th Computational Complexity Conference (CCC’19), volume 137, pp. 7:1-25. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. [doi:10.4230/LIPIcs.CCC.2019.7]6
[24] [24] RUDOLFLIDL ANDHARALDNIEDERREITER:Finite Fields. Cambridge Univ. Press, 1997. [doi:10.1017/CBO9780511525926]41
[25] [25] SHACHARLOVETT:Unconditional pseudorandom generators for low-degree polynomials.Theory of Computing,5(3):69-82, 2009.Preliminary version inSTOC’08. [doi:10.4086/toc.2009.v005a003]2 · Zbl 1213.68274
[26] [26] CHI-JENLU: Improved pseudorandom generators for combinatorial rectangles.Combinatorica, 22(3):417-433, 2002. Preliminary version inICALP’98. [doi:10.1007/s004930200021]3 · Zbl 1012.05047
[27] [27] MICHAELLUBY, BOBANVELI ˇCKOVI ´C,ANDAVIWIGDERSON: Deterministic approximate counting of depth-2 circuits. In2nd Israel Symp. on Theory and Computing Systems (ISTCS’93), pp.
[28] [28] RAGHUMEKA, OMERREINGOLD,ANDAVISHAYTAL: Pseudorandom generators for width-3 branching programs. InProc. 51st STOC. ACM Press, 2019. [doi:10.1145/3313276.3316319, arXiv:1806.04256]6
[29] [29] JOSEPHNAOR ANDMONINAOR: Small-bias probability spaces: efficient constructions and applications.SIAM J. Comput., 22(4):838-856, 1993.Preliminary version inSTOC’90. [doi:10.1137/0222053]4,6,9,14,16,17 · Zbl 0776.60014
[30] [30] NOAMNISAN: Pseudorandom bits for constant depth circuits.Combinatorica, 11(1):63-70, 1991. [doi:10.1007/BF01375474]4 · Zbl 0732.68056
[31] [31] NOAMNISAN: Pseudorandom generators for space-bounded computation.Combinatorica, 12(4):449-461, 1992. Preliminary version inSTOC’90. [doi:10.1007/BF01305237]3,4 · Zbl 0759.68024
[32] [32] NOAMNISAN ANDDAVIDZUCKERMAN: Randomness is linear in space.J. Comput. System Sci., 52(1):43-52, 1996. [doi:10.1006/jcss.1996.0004]3 · Zbl 0846.68041
[33] [33] MICHAELSAKS ANDSHIYUZHOU:BPHSPACE(S)⊆DSPACE(S3/2).J. Comput. System Sci., 58(2):376-403, 1999. Preliminary version inFOCS’95. [doi:10.1006/jcss.1998.1616]3
[34] [34] ROCCOA. SERVEDIO ANDLI-YANGTAN: Improved pseudorandom generators from pseudorandom multi-switching lemmas. InProc. 23rd Internat. Workshop on Randomization and Computation (RANDOM’19), pp. 45:1-45:23. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.45]2 · Zbl 07650112
[35] [35] J. MICHAELSTEELE:The Cauchy-Schwarz Master Class.Cambridge Univ. Press, 2004. [doi:10.1017/CBO9780511817106]21 · Zbl 1060.26023
[36] [36] LUCATREVISAN: Open problems in unconditional derandomization.Slides presented at China Theory Week (CTW’10), 2010.3,6
[37] [37] YOAVTZUR: Notions of weak pseudorandomness andGF(2n)-polynomials. Master’s thesis, Weizmann Institute of Science, 2009. Link atECCC.3
[38] [38] EMANUELEVIOLA: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates.SIAM J. Comput., 36(5):1387-1403, 2007.Preliminary version inCCC’05. [doi:10.1137/050640941]2 · Zbl 1124.68037
[39] [39] EMANUELEVIOLA: The sum ofDsmall-bias generators fools polynomials of degreeD.Comput. Complexity, 18(2):209-217, 2009. Preliminary version inCCC’08. [doi:10.1007/s00037-009-0273 · Zbl 1217.68157
[40] [40] EMANUELEVIOLA: Randomness buys depth for approximate counting.Comput. Complexity, 23(3):479-508, 2014. Preliminary version inFOCS’11. [doi:10.1007/s00037-013-0076-6]3 · Zbl 1318.68091
[41] [41] EMANUELEVIOLA: Special topics in complexity theory. Lecture notes, Northeastern Univ., 2017. ECCC.6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.