×

Pseudorandom generators for combinatorial checkerboards. (English) Zbl 1290.68042

Summary: We define a combinatorial checkerboard to be a function \(f:\{1, \dots ,m\}^d\to\{ 1,-1\}\) of the form \(f(u_1,\dots,u_d)=\prod_{i=1}^df_i(u_i)\) for some functions \(f_i:\{1,\dots ,m\}\to\{ 1,-1\}\). This is a variant of combinatorial rectangles, which can be defined in the same way but using \(\{ 0,1\}\) instead of \(\{ 1,-1\}\). We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case \(m=2\). We construct a pseudorandom generator that \(\epsilon\)-fools all combinatorial checkerboards with seed length \(O\left(\log m+\log d\cdot\log\log d+\log^{3/2} \frac{1}{\epsilon}\right)\). Previous work by R. Impagliazzo, N. Nisan and A. Wigderson [“Pseudorandomness for network algorithms”, in: STOC ‘94. Proceedings of the 26th ACM Symposium on Theory of Computing. New York, NY, USA, 1994. New York, NY: ACM. 356–364 (1994; doi:10.1145/195058.195190)] implies a pseudorandom generator with seed length \(O\left(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\right)\). Our seed length is better except when \(\frac{1}{\epsilon}\geq d^{\omega(\log d)}\).

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Full Text: DOI

References:

[1] Scott Aaronson, Dieter van Melkebeek (2011) On Circuit Lower Bounds from Derandomization. Theory of Computing 7(1): 177-184 · Zbl 1247.68091 · doi:10.4086/toc.2011.v007a012
[2] Miklós Ajtai, János Komlós, & Endre Szemerédi (1987). Deterministic Simulation in LOGSPACE. In Proceedings of the 19th ACM Symposium on Theory of Computing, 132-140. · Zbl 1247.68091
[3] Miklós Ajtai, Avi Wigderson (1989) Deterministic Simulation of Probabilistic Constant-Depth Circuits. Advances in Computing Research—Randomness and Computation 5: 199-223
[4] Noga Alon, Fan Chung (1988) Explicit Construction of Linear Sized Tolerant Networks. Discrete Mathematics 72(1-3): 15-19 · Zbl 0657.05068 · doi:10.1016/0012-365X(88)90189-6
[5] Noga Alon, Zvi Galil, Vitali Milman (1987) Better Expanders and Superconcentrators. Journal of Algorithms 8(3): 337-347 · Zbl 0641.68102 · doi:10.1016/0196-6774(87)90014-9
[6] Noga Alon, Oded Goldreich, Johan Håstad, René Peralta (1992) Simple Constructions of Almost k-wise Independent Random Variables. Random Structures and Algorithms 3(3): 289-304 · Zbl 0755.60002 · doi:10.1002/rsa.3240030308
[7] Noga Alon, Vitali Milman (1985) λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators. Journal of Combinatorial Theory, Series B 38(1): 73-88 · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9
[8] Roy Armoni (1998). On the Derandomization of Space-Bounded Computations. In Proceedings of the 2nd International Workshop on Randomization and Computation, 47-59. · Zbl 0946.68041
[9] Roy Armoni, Michael Saks, Avi Wigderson & Shiyu Zhou (1996). Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 412-421. · Zbl 0814.68098
[10] Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou (2000) An O(log4/3(n)) Space Algorithm for (s,t) Connectivity in Undirected Graphs. Journal of the ACM 47(2): 294-311 · Zbl 1133.68341 · doi:10.1145/333979.333984
[11] László Babai, Lance Fortnow, NoamNisan& Avi Wigderson (1993) BPP Has Subexponential Time Simulations Unless EXPTIME Has Publishable Proofs. Computational Complexity 3: 307-318 · Zbl 0802.68054 · doi:10.1007/BF01275486
[12] László Babai, Noam Nisan, Mario Szegedy (1992) Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. Journal of Computer and System Sciences 45(2): 204-232 · Zbl 0769.68040 · doi:10.1016/0022-0000(92)90047-M
[13] Louay Bazzi (2009) Polylogarithmic Independence Can Fool DNF Formulas. SIAM Journal on Computing 38(6): 2220-2272 · Zbl 1188.68156 · doi:10.1137/070691954
[14] Mihir Bellare & John Rompel (1994). Randomness-Efficient Oblivious Sampling. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, 276-287. · Zbl 0708.05030
[15] Andrej Bogdanov (2005). Pseudorandom Generators for Low Degree Polynomials. In Proceedings of the 37th ACM Symposium on Theory of Computing, 21-30. · Zbl 1192.68348
[16] Andrej Bogdanov, Zeev Dvir, Elad Verbin & Amir Yehudayoff (2009). Pseudorandomness for Width 2 Branching Programs. Technical Report TR09-070, Electronic Colloquium on Computational Complexity. · Zbl 1300.68037
[17] Andrej Bogdanov, Periklis Papakonstantinou & Andrew Wan (2011). Pseudorandomness for Read-Once Formulas. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (to appear). · Zbl 1292.68110
[18] Andrej Bogdanov, Emanuele Viola (2010) Pseudorandom Bits for Polynomials. SIAM Journal on Computing 39(6): 2464-2486 · Zbl 1211.68215 · doi:10.1137/070712109
[19] Mark Braverman (2010). Polylogarithmic Independence Fools AC0 Circuits. Journal of the ACM57(5). · Zbl 1327.68108
[20] Mark Braverman, Anup Rao, Ran Raz & Amir Yehudayoff (2010). Pseudorandom Generators for Regular Branching Programs. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, 40-47. · Zbl 0759.68024
[21] Joshua Brody & Elad Verbin (2010). The Coin Problem, and Pseudorandomness for Branching Programs. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, 30-39. · Zbl 0846.68041
[22] Jin-Yi Cai, Venkatesan Chakaravarthy, Dieter van Melkebeek (2006) Time-Space Tradeoff in Derandomizing Probabilistic Logspace. Theory of Computing Systems 39(1): 189-208 · Zbl 1101.68109 · doi:10.1007/s00224-005-1264-9
[23] Anindya De (2011). Pseudorandomness for Permutation and Regular Branching Programs. In Proceedings of the 26th IEEE Conference on Computational Complexity, 221-231. · Zbl 0661.05035
[24] Anindya De, Omid Etesami, Luca Trevisan & Madhur Tulsiani (2010). Improved Pseudorandom Generators for Depth 2 Circuits. In Proceedings of the 14th International Workshop on Randomization and Computation, 504-517. · Zbl 1305.68128
[25] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola (2010a) Bounded Independence Fools Halfspaces. SIAM Journal on Computing 39(8): 3441-3462 · Zbl 1221.68169 · doi:10.1137/100783030
[26] Ilias Diakonikolas, Daniel Kane & Jelani Nelson (2010b). Bounded Independence Fools Degree-2 Threshold Functions. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, 11-20.
[27] Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic (1998) Efficient Approximation of Product Distributions. Random Structures and Algorithms 13(1): 1-16 · Zbl 0959.68553
[28] Lance Fortnow, Adam Klivans (2006). Linear Advice for Randomized Logarithmic Space. In Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, 469-476. · Zbl 1136.68404
[29] Ofer Gabber, Zvi Galil (1981) Explicit Constructions of Linear-Sized Superconcentrators. Journal of Computer and System Sciences 22(3): 407-420 · Zbl 0487.05045 · doi:10.1016/0022-0000(81)90040-4
[30] Oded Goldreich (2011). In a World of P = BPP. Studies in Complexity and Cryptography 191-232. · Zbl 1343.68084
[31] Oded Goldreich, Avi Wigderson (1997) Tiny Families of Functions with Random Properties: A Quality-Size Trade-Off for Hashing. Random Structures and Algorithms 11(4): 315-343 · Zbl 0891.60010 · doi:10.1002/(SICI)1098-2418(199712)11:4<315::AID-RSA3>3.0.CO;2-1
[32] Parikshit Gopalan, Raghu Meka, Omer Reingold & David Zuckerman (2011). Pseudorandom Generators for Combinatorial Shapes. In Proceedings of the 43rd ACM Symposium on Theory of Computing, 253-262. · Zbl 1288.68226
[33] Parikshit Gopalan, Ryan O’Donnell, Yi Wu & David Zuckerman (2010). Fooling Functions of Halfspaces under Product Distributions. In Proceedings of the 25th IEEE Conference on Computational Complexity, 223-234. · Zbl 0732.68056
[34] Prahladh Harsha, Adam Klivans & Raghu Meka (2010). An Invariance Principle for Polytopes. In Proceedings of the 42nd ACM Symposium on Theory of Computing, 543-552. · Zbl 1293.68224
[35] Russell Impagliazzo, Valentine Kabanets (2004) Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1-2): 1-46 · Zbl 1089.68042 · doi:10.1007/s00037-004-0182-6
[36] Russell Impagliazzo, Valentine Kabanets, Avi Wigderson (2002) In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. Journal of Computer and System Sciences 65(4): 672-694 · Zbl 1059.68047 · doi:10.1016/S0022-0000(02)00024-7
[37] Russell Impagliazzo, Noam Nisan & Avi Wigderson (1994). Pseudorandomness for Network Algorithms. In Proceedings of the 26th ACM Symposium on Theory of Computing, 356-364. · Zbl 1345.68269
[38] Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson (2006) Reducing the Seed Length in the Nisan-Wigderson Generator.. Combinatorica 26(6): 647-681 · Zbl 1121.68052 · doi:10.1007/s00493-006-0036-8
[39] Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the 29th ACM Symposium on Theory of Computing, 220-229. · Zbl 0962.68058
[40] Shuji Jimbo, Akira Maruoka (1987) Expanders Obtained from Affine Transformations. Combinatorica 7(4): 343-355 · Zbl 0637.05017 · doi:10.1007/BF02579322
[41] Adam Klivans (2001). On the Derandomization of Constant Depth Circuits. In Proceedings of the 5th International Workshop on Randomization and Computation, 249-260. · Zbl 0998.68061
[42] Michal Koucký, Prajakta Nimbhorkar & Pavel Pudlák (2011). Pseudorandom Generators for Group Products. In Proceedings of the 43rd ACM Symposium on Theory of Computing, 263-272. · Zbl 1288.68131
[43] Nathan Linial, Michael Luby, Michael Saks, David Zuckerman (1997) Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Combinatorica 17(2): 215-234 · Zbl 0886.68076 · doi:10.1007/BF01200907
[44] Shachar Lovett (2009) Unconditional Pseudorandom Generators for Low Degree Polynomials. Theory of Computing 5(1): 69-82 · Zbl 1213.68274 · doi:10.4086/toc.2009.v005a003
[45] Shachar Lovett, Partha Mukhopadhyay & Amir Shpilka (2010). Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, 695-704. · Zbl 1290.68049
[46] Shachar Lovett, Omer Reingold, Luca Trevisan & Salil Vadhan (2009). Pseudorandom Bit Generators That Fool Modular Sums. In Proceedings of the 13th International Workshop on Randomization and Computation, 615-630. · Zbl 1255.68294
[47] Chi-Jen Lu (2002) Improved Pseudorandom Generators for Combinatorial Rectangles. Combinatorica 22(3): 417-434 · Zbl 1012.05047 · doi:10.1007/s004930200021
[48] Alexander Lubotzky, Ralph Phillips, Peter Sarnak (1988) Ramanujan Graphs. Combinatorica 8(3): 261-277 · Zbl 0661.05035 · doi:10.1007/BF02126799
[49] Michael Luby, Boban Velickovic (1996) On Deterministic Approximation of DNF. Algorithmica 16(4-5): 415-433 · Zbl 0857.68054
[50] Michael Luby, Boban Velickovic & Avi Wigderson (1993). Deterministic Approximate Counting of Depth-2 Circuits. In Proceedings of the 2nd Israel Symposium on Theory of Computing Systems, 18-24. · Zbl 0802.68054
[51] Gregory Margulis (1973) Explicit Constructions of Expanders. Problemy Peredaci Informacii 9(4): 71-80 · Zbl 0312.22011
[52] Gregory Margulis (1988) Explicit Group-Theoretic Constructions of Combinatorial Schemes and Their Applications in the Construction of Expanders and Concentrators. Problems of Information Transmission 24(1): 39-46 · Zbl 0708.05030
[53] Raghu Meka & David Zuckerman (2009). Small-Bias Spaces for Group Products. In Proceedings of the 13th International Workshop on Randomization and Computation, 658-672. · Zbl 1255.68102
[54] Raghu Meka & David Zuckerman (2010). Pseudorandom Generators for Polynomial Threshold Functions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, 427-436. · Zbl 1293.65010
[55] Moshe Morgenstern (1994) Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q. Journal of Combinatorial Theory, Series B 62(1): 44-62 · Zbl 0814.68098 · doi:10.1006/jctb.1994.1054
[56] Elchanan Mossel, Amir Shpilka, Luca Trevisan (2006) On Epsilon-Biased Generators in NC0. Random Structures and Algorithms 29(1): 56-81 · Zbl 1102.68024 · doi:10.1002/rsa.20112
[57] Joseph Naor, Moni Naor (1993) Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM Journal on Computing 22(4): 838-856 · Zbl 0776.60014 · doi:10.1137/0222053
[58] Noam Nisan (1991) Pseudorandom Bits for Constant Depth Circuits. Combinatorica 11(1): 63-70 · Zbl 0732.68056 · doi:10.1007/BF01375474
[59] Noam Nisan (1992) Pseudorandom Generators for Space-Bounded Computation. Combinatorica 12(4): 449-461 · Zbl 0759.68024 · doi:10.1007/BF01305237
[60] Noam Nisan (1993) On Read-Once vs. Multiple Access to Randomness in Logspace. Theoretical Computer Science 107(1): 135-144 · Zbl 0774.68037
[61] Noam Nisan \[(1994) {{\rm RL} \subseteq{\rm SC}} \] . Computational Complexity 4: 1-11 · Zbl 0806.68043 · doi:10.1007/BF01205052
[62] Noam Nisan, Endre Szemerédi & Avi Wigderson (1992). Undirected Connectivity in O(log1.5(n)) Space. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, 24-29. · Zbl 0915.05081
[63] Noam Nisan, Avi Wigderson (1994) Hardness vs. Randomness. Journal of Computer and System Sciences 49(2): 149-167 · Zbl 0821.68057 · doi:10.1016/S0022-0000(05)80043-1
[64] Noam Nisan, David Zuckerman (1996) Randomness is Linear in Space. Journal of Computer and System Sciences 52(1): 43-52 · Zbl 0846.68041 · doi:10.1006/jcss.1996.0004
[65] Ran Raz & Omer Reingold (1999). On Recycling the Randomness of States in Space Bounded Computation. In Proceedings of the 31st ACM Symposium on Theory of Computing, 159-168. · Zbl 1345.68135
[66] Alexander Razborov (2009). A Simple Proof of Bazzi’s Theorem. ACM Transactions on Computation Theory1(1). · Zbl 1322.68108
[67] Omer Reingold (2008). Undirected Connectivity in Log-Space. Journal of the ACM55(4). · Zbl 1315.68156
[68] Omer Reingold, Luca Trevisan & Salil Vadhan (2006). Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem. In Proceedings of the 38th ACM Symposium on Theory of Computing, 457-466. · Zbl 1301.05317
[69] Omer Reingold, Salil Vadhan, Avi Wigderson (2002) Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders. Annals of Mathematics 155(1): 157-187 · Zbl 1008.05101 · doi:10.2307/3062153
[70] Eyal Rozenman & Salil Vadhan (2005). Derandomized Squaring of Graphs. In Proceedings of the 9th International Workshop on Randomization and Computation, 436-447. · Zbl 1142.05331
[71] Michael Saks, Shiyu Zhou \[(1999) {{\rm BP_HSPACE}(S)\subseteq{\rm DSPACE}(S^{3/2})} \]. Journal of Computer and System Sciences 58(2): 376-403 · Zbl 0922.68083 · doi:10.1006/jcss.1998.1616
[72] Ronen Shaltiel, Christopher Umans (2005) Simple Extractors for All Min-Entropies and a New Pseudorandom Generator. Journal of the ACM 52(2): 172-216 · Zbl 1317.68132 · doi:10.1145/1059513.1059516
[73] Jiri Sima & Stanislav Zak (2010). A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3. Technical Report TR10-088, Electronic Colloquium on Computational Complexity. · Zbl 1302.68118
[74] Madhu Sudan, Luca Trevisan, Salil Vadhan (2001) Pseudorandom Generators without the XOR Lemma. Journal of Computer and System Sciences 62(2): 236-266 · Zbl 1005.65006 · doi:10.1006/jcss.2000.1730
[75] Luca Trevisan (2004). A Note on Approximate Counting for k-DNF. In Proceedings of the 8th International Workshop on Randomization and Computation, 417-426. · Zbl 1106.68427
[76] Christopher Umans (2003) Pseudo-random Generators for All Hardnesses. Journal of Computer and System Sciences 67(2): 419-440 · Zbl 1072.68129 · doi:10.1016/S0022-0000(03)00046-1
[77] Salil Vadhan (2011). Pseudorandomness. Manuscript in preparation for Foundations and Trends in Theoretical Computer Science. · Zbl 1252.68206
[78] Emanuele Viola (2007) Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates. SIAM Journal on Computing 36(5): 1387-1403 · Zbl 1124.68037 · doi:10.1137/050640941
[79] Emanuele Viola (2009) The Sum of d Small-Bias Generators Fools Polynomials of Degree d. Computational Complexity 18(2): 209-217 · Zbl 1217.68157 · doi:10.1007/s00037-009-0273-5
[80] Thomas Watson (2011). Pseudorandom Generators for Combinatorial Checkerboards. In Proceedings of the 26th IEEE Conference on Computational Complexity, 232-242.
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.