{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T20:10:30Z","timestamp":1672517430500},"reference-count":80,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,2,4]],"date-time":"2012-02-04T00:00:00Z","timestamp":1328313600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,12]]},"DOI":"10.1007\/s00037-012-0036-6","type":"journal-article","created":{"date-parts":[[2012,2,3]],"date-time":"2012-02-03T02:21:13Z","timestamp":1328235673000},"page":"727-769","source":"Crossref","is-referenced-by-count":3,"title":["Pseudorandom generators for combinatorial checkerboards"],"prefix":"10.1007","volume":"22","author":[{"given":"Thomas","family":"Watson","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,4]]},"reference":[{"issue":"1","key":"36_CR1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.4086\/toc.2011.v007a012","volume":"7","author":"Aaronson Scott","year":"2011","unstructured":"Scott Aaronson, Dieter van Melkebeek (2011) On Circuit Lower Bounds from Derandomization. Theory of Computing 7(1): 177\u2013184","journal-title":"Theory of Computing"},{"key":"36_CR2","unstructured":"Mikl\u00f3s Ajtai, J\u00e1nos Koml\u00f3s, & Endre Szemer\u00e9di (1987). Deterministic Simulation in LOGSPACE. In Proceedings of the 19th ACM Symposium on Theory of Computing, 132\u2013140."},{"key":"36_CR3","first-page":"199","volume":"5","author":"Ajtai Mikl\u00f3s","year":"1989","unstructured":"Mikl\u00f3s Ajtai, Avi Wigderson (1989) Deterministic Simulation of Probabilistic Constant-Depth Circuits. Advances in Computing Research\u2014Randomness and Computation 5: 199\u2013223","journal-title":"Advances in Computing Research\u2014Randomness and Computation"},{"issue":"1-3","key":"36_CR4","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0012-365X(88)90189-6","volume":"72","author":"Alon Noga","year":"1988","unstructured":"Noga Alon, Fan Chung (1988) Explicit Construction of Linear Sized Tolerant Networks. Discrete Mathematics 72(1-3): 15\u201319","journal-title":"Discrete Mathematics"},{"issue":"3","key":"36_CR5","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0196-6774(87)90014-9","volume":"8","author":"Alon Noga","year":"1987","unstructured":"Noga Alon, Zvi Galil, Vitali Milman (1987) Better Expanders and Superconcentrators. Journal of Algorithms 8(3): 337\u2013347","journal-title":"Journal of Algorithms"},{"issue":"3","key":"36_CR6","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"Alon Noga","year":"1992","unstructured":"Noga Alon, Oded Goldreich, Johan H\u00e5stad, Ren\u00e9 Peralta (1992) Simple Constructions of Almost k-wise Independent Random Variables. Random Structures and Algorithms 3(3): 289\u2013304","journal-title":"Random Structures and Algorithms"},{"issue":"1","key":"36_CR7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"Alon Noga","year":"1985","unstructured":"Noga Alon, Vitali Milman (1985) \u03bb1, Isoperimetric Inequalities for Graphs, and Superconcentrators. Journal of Combinatorial Theory, Series B 38(1): 73\u201388","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"36_CR8","doi-asserted-by":"crossref","unstructured":"Roy Armoni (1998). On the Derandomization of Space-Bounded Computations. In Proceedings of the 2nd International Workshop on Randomization and Computation, 47\u201359.","DOI":"10.1007\/3-540-49543-6_5"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013421.","DOI":"10.1109\/SFCS.1996.548500"},{"issue":"2","key":"36_CR10","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/333979.333984","volume":"47","author":"Armoni Roy","year":"2000","unstructured":"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\u2013311","journal-title":"Journal of the ACM"},{"key":"36_CR11","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"Babai L\u00e1szl\u00f3","year":"1993","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, NoamNisan& Avi Wigderson (1993) BPP Has Subexponential Time Simulations Unless EXPTIME Has Publishable Proofs. Computational Complexity 3: 307\u2013318","journal-title":"Computational Complexity"},{"issue":"2","key":"36_CR12","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"Babai L\u00e1szl\u00f3","year":"1992","unstructured":"L\u00e1szl\u00f3 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\u2013232","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"36_CR13","doi-asserted-by":"crossref","first-page":"2220","DOI":"10.1137\/070691954","volume":"38","author":"Bazzi Louay","year":"2009","unstructured":"Louay Bazzi (2009) Polylogarithmic Independence Can Fool DNF Formulas. SIAM Journal on Computing 38(6): 2220\u20132272","journal-title":"SIAM Journal on Computing"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Mihir Bellare & John Rompel (1994). Randomness-Efficient Oblivious Sampling. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, 276\u2013287.","DOI":"10.1109\/SFCS.1994.365687"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov (2005). Pseudorandom Generators for Low Degree Polynomials. In Proceedings of the 37th ACM Symposium on Theory of Computing, 21\u201330.","DOI":"10.1145\/1060590.1060594"},{"key":"36_CR16","unstructured":"Andrej Bogdanov, Zeev Dvir, Elad Verbin & Amir Yehudayoff (2009). Pseudorandomness for Width 2 Branching Programs. Technical Report TR09-070, Electronic Colloquium on Computational Complexity."},{"key":"36_CR17","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1109\/FOCS.2011.57"},{"issue":"6","key":"36_CR18","doi-asserted-by":"crossref","first-page":"2464","DOI":"10.1137\/070712109","volume":"39","author":"Bogdanov Andrej","year":"2010","unstructured":"Andrej Bogdanov, Emanuele Viola (2010) Pseudorandom Bits for Polynomials. SIAM Journal on Computing 39(6): 2464\u20132486","journal-title":"SIAM Journal on Computing"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Mark Braverman (2010). Polylogarithmic Independence Fools AC0 Circuits. Journal of the ACM 57(5).","DOI":"10.1145\/1754399.1754401"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"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\u201347.","DOI":"10.1109\/FOCS.2010.11"},{"key":"36_CR21","unstructured":"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\u201339."},{"issue":"1","key":"36_CR22","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s00224-005-1264-9","volume":"39","author":"Cai Jin-Yi","year":"2006","unstructured":"Jin-Yi Cai, Venkatesan Chakaravarthy, Dieter van Melkebeek (2006) Time-Space Tradeoff in Derandomizing Probabilistic Logspace. Theory of Computing Systems 39(1): 189\u2013208","journal-title":"Theory of Computing Systems"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Anindya De (2011). Pseudorandomness for Permutation and Regular Branching Programs. In Proceedings of the 26th IEEE Conference on Computational Complexity, 221\u2013231.","DOI":"10.1109\/CCC.2011.23"},{"key":"36_CR24","doi-asserted-by":"crossref","unstructured":"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\u2013517.","DOI":"10.1007\/978-3-642-15369-3_38"},{"issue":"8","key":"36_CR25","doi-asserted-by":"crossref","first-page":"3441","DOI":"10.1137\/100783030","volume":"39","author":"Diakonikolas Ilias","year":"2010","unstructured":"Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola (2010a) Bounded Independence Fools Halfspaces. SIAM Journal on Computing 39(8): 3441\u20133462","journal-title":"SIAM Journal on Computing"},{"key":"36_CR26","doi-asserted-by":"crossref","unstructured":"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\u201320.","DOI":"10.1109\/FOCS.2010.8"},{"issue":"1","key":"36_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","volume":"13","author":"Even Guy","year":"1998","unstructured":"Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic (1998) Efficient Approximation of Product Distributions. Random Structures and Algorithms 13(1): 1\u201316","journal-title":"Random Structures and Algorithms"},{"key":"36_CR28","doi-asserted-by":"crossref","unstructured":"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\u2013476.","DOI":"10.1007\/11672142_38"},{"issue":"3","key":"36_CR29","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"Gabber Ofer","year":"1981","unstructured":"Ofer Gabber, Zvi Galil (1981) Explicit Constructions of Linear-Sized Superconcentrators. Journal of Computer and System Sciences 22(3): 407\u2013420","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR30","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2011). In a World of P\u00a0=\u00a0BPP. Studies in Complexity and Cryptography 191\u2013232.","DOI":"10.1007\/978-3-642-22670-0_20"},{"issue":"4","key":"36_CR31","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<315::AID-RSA3>3.0.CO;2-1","volume":"11","author":"Goldreich Oded","year":"1997","unstructured":"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\u2013343","journal-title":"Random Structures and Algorithms"},{"key":"36_CR32","doi-asserted-by":"crossref","unstructured":"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\u2013262.","DOI":"10.1145\/1993636.1993671"},{"key":"36_CR33","doi-asserted-by":"crossref","unstructured":"Parikshit Gopalan, Ryan O\u2019Donnell, Yi Wu & David Zuckerman (2010). Fooling Functions of Halfspaces under Product Distributions. In Proceedings of the 25th IEEE Conference on Computational Complexity, 223\u2013234.","DOI":"10.1109\/CCC.2010.29"},{"key":"36_CR34","doi-asserted-by":"crossref","unstructured":"Prahladh Harsha, Adam Klivans & Raghu Meka (2010). An Invariance Principle for Polytopes. In Proceedings of the 42nd ACM Symposium on Theory of Computing, 543\u2013552.","DOI":"10.1145\/1806689.1806764"},{"issue":"1-2","key":"36_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"Impagliazzo Russell","year":"2004","unstructured":"Russell Impagliazzo, Valentine Kabanets (2004) Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1-2): 1\u201346","journal-title":"Computational Complexity"},{"issue":"4","key":"36_CR36","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"Impagliazzo Russell","year":"2002","unstructured":"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\u2013694","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR37","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Noam Nisan & Avi Wigderson (1994). Pseudorandomness for Network Algorithms. In Proceedings of the 26th ACM Symposium on Theory of Computing, 356\u2013364.","DOI":"10.1145\/195058.195190"},{"issue":"6","key":"36_CR38","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1007\/s00493-006-0036-8","volume":"26","author":"Impagliazzo Russell","year":"2006","unstructured":"Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson (2006) Reducing the Seed Length in the Nisan-Wigderson Generator.. Combinatorica 26(6): 647\u2013681","journal-title":"Combinatorica"},{"key":"36_CR39","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P\u00a0=\u00a0BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the 29th ACM Symposium on Theory of Computing, 220\u2013229."},{"issue":"4","key":"36_CR40","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02579322","volume":"7","author":"Jimbo Shuji","year":"1987","unstructured":"Shuji Jimbo, Akira Maruoka (1987) Expanders Obtained from Affine Transformations. Combinatorica 7(4): 343\u2013355","journal-title":"Combinatorica"},{"key":"36_CR41","doi-asserted-by":"crossref","unstructured":"Adam Klivans (2001). On the Derandomization of Constant Depth Circuits. In Proceedings of the 5th International Workshop on Randomization and Computation, 249\u2013260.","DOI":"10.1007\/3-540-44666-4_28"},{"key":"36_CR42","doi-asserted-by":"crossref","unstructured":"Michal Kouck\u00fd, Prajakta Nimbhorkar & Pavel Pudl\u00e1k (2011). Pseudorandom Generators for Group Products. In Proceedings of the 43rd ACM Symposium on Theory of Computing, 263\u2013272.","DOI":"10.1145\/1993636.1993672"},{"issue":"2","key":"36_CR43","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200907","volume":"17","author":"Linial Nathan","year":"1997","unstructured":"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\u2013234","journal-title":"Combinatorica"},{"issue":"1","key":"36_CR44","doi-asserted-by":"crossref","first-page":"69","DOI":"10.4086\/toc.2009.v005a003","volume":"5","author":"Lovett Shachar","year":"2009","unstructured":"Shachar Lovett (2009) Unconditional Pseudorandom Generators for Low Degree Polynomials. Theory of Computing 5(1): 69\u201382","journal-title":"Theory of Computing"},{"key":"36_CR45","doi-asserted-by":"crossref","unstructured":"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\u2013704.","DOI":"10.1109\/FOCS.2010.72"},{"key":"36_CR46","doi-asserted-by":"crossref","unstructured":"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\u2013630.","DOI":"10.1007\/978-3-642-03685-9_46"},{"issue":"3","key":"36_CR47","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s004930200021","volume":"22","author":"Lu Chi-Jen","year":"2002","unstructured":"Chi-Jen Lu (2002) Improved Pseudorandom Generators for Combinatorial Rectangles. Combinatorica 22(3): 417\u2013434","journal-title":"Combinatorica"},{"issue":"3","key":"36_CR48","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"Lubotzky Alexander","year":"1988","unstructured":"Alexander Lubotzky, Ralph Phillips, Peter Sarnak (1988) Ramanujan Graphs. Combinatorica 8(3): 261\u2013277","journal-title":"Combinatorica"},{"issue":"4-5","key":"36_CR49","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/BF01940873","volume":"16","author":"Luby Michael","year":"1996","unstructured":"Michael Luby, Boban Velickovic (1996) On Deterministic Approximation of DNF. Algorithmica 16(4-5): 415\u2013433","journal-title":"Algorithmica"},{"key":"36_CR50","doi-asserted-by":"crossref","unstructured":"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\u201324.","DOI":"10.1109\/ISTCS.1993.253488"},{"issue":"4","key":"36_CR51","first-page":"71","volume":"9","author":"Margulis Gregory","year":"1973","unstructured":"Gregory Margulis (1973) Explicit Constructions of Expanders. Problemy Peredaci Informacii 9(4): 71\u201380","journal-title":"Problemy Peredaci Informacii"},{"issue":"1","key":"36_CR52","first-page":"39","volume":"24","author":"Margulis Gregory","year":"1988","unstructured":"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\u201346","journal-title":"Problems of Information Transmission"},{"key":"36_CR53","unstructured":"Raghu Meka & David Zuckerman (2009). Small-Bias Spaces for Group Products. In Proceedings of the 13th International Workshop on Randomization and Computation, 658\u2013672."},{"key":"36_CR54","unstructured":"Raghu Meka & David Zuckerman (2010). Pseudorandom Generators for Polynomial Threshold Functions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, 427\u2013436."},{"issue":"1","key":"36_CR55","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1006\/jctb.1994.1054","volume":"62","author":"Morgenstern Moshe","year":"1994","unstructured":"Moshe Morgenstern (1994) Existence and Explicit Constructions of q\u00a0+\u00a01 Regular Ramanujan Graphs for Every Prime Power q. Journal of Combinatorial Theory, Series B 62(1): 44\u201362","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"36_CR56","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"Mossel Elchanan","year":"2006","unstructured":"Elchanan Mossel, Amir Shpilka, Luca Trevisan (2006) On Epsilon-Biased Generators in NC0. Random Structures and Algorithms 29(1): 56\u201381","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"36_CR57","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"Naor Joseph","year":"1993","unstructured":"Joseph Naor, Moni Naor (1993) Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM Journal on Computing 22(4): 838\u2013856","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"36_CR58","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"Nisan Noam","year":"1991","unstructured":"Noam Nisan (1991) Pseudorandom Bits for Constant Depth Circuits. Combinatorica 11(1): 63\u201370","journal-title":"Combinatorica"},{"issue":"4","key":"36_CR59","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"Nisan Noam","year":"1992","unstructured":"Noam Nisan (1992) Pseudorandom Generators for Space-Bounded Computation. Combinatorica 12(4): 449\u2013461","journal-title":"Combinatorica"},{"issue":"1","key":"36_CR60","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(93)90258-U","volume":"107","author":"Nisan Noam","year":"1993","unstructured":"Noam Nisan (1993) On Read-Once vs. Multiple Access to Randomness in Logspace. Theoretical Computer Science 107(1): 135\u2013144","journal-title":"Multiple Access to Randomness in Logspace. Theoretical Computer Science"},{"key":"36_CR61","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01205052","volume":"4","author":"Nisan Noam","year":"1994","unstructured":"Noam Nisan (1994) $${{\\rm RL} \\subseteq {\\rm SC}}$$ . Computational Complexity 4: 1\u201311","journal-title":"Computational Complexity"},{"key":"36_CR62","unstructured":"Noam Nisan, Endre Szemer\u00e9di & Avi Wigderson (1992). Undirected Connectivity in O(log1.5(n)) Space. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, 24\u201329."},{"issue":"2","key":"36_CR63","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Nisan Noam","year":"1994","unstructured":"Noam Nisan, Avi Wigderson (1994) Hardness vs. Randomness. Journal of Computer and System Sciences 49(2): 149\u2013167","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"36_CR64","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"Nisan Noam","year":"1996","unstructured":"Noam Nisan, David Zuckerman (1996) Randomness is Linear in Space. Journal of Computer and System Sciences 52(1): 43\u201352","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR65","unstructured":"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\u2013168."},{"key":"36_CR66","doi-asserted-by":"crossref","unstructured":"Alexander Razborov (2009). A Simple Proof of Bazzi\u2019s Theorem. ACM Transactions on Computation Theory 1(1).","DOI":"10.1145\/1490270.1490273"},{"key":"36_CR67","doi-asserted-by":"crossref","unstructured":"Omer Reingold (2008). Undirected Connectivity in Log-Space. Journal of the ACM 55(4).","DOI":"10.1145\/1391289.1391291"},{"key":"36_CR68","unstructured":"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\u2013466."},{"issue":"1","key":"36_CR69","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"Reingold Omer","year":"2002","unstructured":"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\u2013187","journal-title":"Annals of Mathematics"},{"key":"36_CR70","unstructured":"Eyal Rozenman & Salil Vadhan (2005). Derandomized Squaring of Graphs. In Proceedings of the 9th International Workshop on Randomization and Computation, 436\u2013447."},{"issue":"2","key":"36_CR71","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1006\/jcss.1998.1616","volume":"58","author":"Saks Michael","year":"1999","unstructured":"Michael Saks, Shiyu Zhou (1999) $${{\\rm BP_HSPACE}(S)\\subseteq{\\rm DSPACE}(S^{3\/2})}$$ . Journal of Computer and System Sciences 58(2): 376\u2013403","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"36_CR72","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/1059513.1059516","volume":"52","author":"Shaltiel Ronen","year":"2005","unstructured":"Ronen Shaltiel, Christopher Umans (2005) Simple Extractors for All Min-Entropies and a New Pseudorandom Generator. Journal of the ACM 52(2): 172\u2013216","journal-title":"Journal of the ACM"},{"key":"36_CR73","unstructured":"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."},{"issue":"2","key":"36_CR74","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"Sudan Madhu","year":"2001","unstructured":"Madhu Sudan, Luca Trevisan, Salil Vadhan (2001) Pseudorandom Generators without the XOR Lemma. Journal of Computer and System Sciences 62(2): 236\u2013266","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR75","doi-asserted-by":"crossref","unstructured":"Luca Trevisan (2004). A Note on Approximate Counting for k-DNF. In Proceedings of the 8th International Workshop on Randomization and Computation, 417\u2013426.","DOI":"10.1007\/978-3-540-27821-4_37"},{"issue":"2","key":"36_CR76","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/S0022-0000(03)00046-1","volume":"67","author":"Umans Christopher","year":"2003","unstructured":"Christopher Umans (2003) Pseudo-random Generators for All Hardnesses. Journal of Computer and System Sciences 67(2): 419\u2013440","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR77","unstructured":"Salil Vadhan (2011). Pseudorandomness. Manuscript in preparation for Foundations and Trends in Theoretical Computer Science."},{"issue":"5","key":"36_CR78","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1137\/050640941","volume":"36","author":"Viola Emanuele","year":"2007","unstructured":"Emanuele Viola (2007) Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates. SIAM Journal on Computing 36(5): 1387\u20131403","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"36_CR79","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s00037-009-0273-5","volume":"18","author":"Viola Emanuele","year":"2009","unstructured":"Emanuele Viola (2009) The Sum of d Small-Bias Generators Fools Polynomials of Degree d. Computational Complexity 18(2): 209\u2013217","journal-title":"Computational Complexity"},{"key":"36_CR80","doi-asserted-by":"crossref","unstructured":"Thomas Watson (2011). Pseudorandom Generators for Combinatorial Checkerboards. In Proceedings of the 26th IEEE Conference on Computational Complexity, 232\u2013242.","DOI":"10.1109\/CCC.2011.12"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0036-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0036-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0036-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T01:34:17Z","timestamp":1561253657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0036-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,4]]},"references-count":80,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["36"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0036-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,4]]}}}