{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:59:24Z","timestamp":1775282364657,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403279","type":"print"},{"value":"9783642403286","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_45","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"655-670","source":"Crossref","is-referenced-by-count":14,"title":["Pseudorandomness for Regular Branching Programs via Fourier Analysis"],"prefix":"10.1007","author":[{"given":"Omer","family":"Reingold","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Steinke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"45_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P. Indyk","year":"2006","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM\u00a053(3), 307\u2013323 (2006)","journal-title":"J. ACM"},{"key":"45_CR2","doi-asserted-by":"crossref","unstructured":"Sivakumar, D.: Algorithmic derandomization via complexity theory. In: CCC 2002, p.\u00a010 (2002)","DOI":"10.1145\/509907.509996"},{"key":"45_CR3","doi-asserted-by":"crossref","unstructured":"Celis, L.E., Reingold, O., Segev, G., Wieder, U.: Balls and bins: Smaller hash families and faster evaluation. In: FOCS 2011, pp. 599\u2013608 (2011)","DOI":"10.1109\/FOCS.2011.49"},{"issue":"4","key":"45_CR4","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1137\/S0097539705447281","volume":"35","author":"A. Healy","year":"2006","unstructured":"Healy, A., Vadhan, S., Viola, E.: Using nondeterminism to amplify hardness. SIAM Journal on Computing\u00a035(4), 903\u2013931 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/11538462_30","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Kaplan","year":"2005","unstructured":"Kaplan, E., Naor, M., Reingold, O.: Derandomized constructions of k-wise (almost) independent permutations. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 354\u2013365. Springer, Heidelberg (2005)"},{"key":"45_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/11818175_2","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"I. Haitner","year":"2006","unstructured":"Haitner, I., Harnik, D., Reingold, O.: On the power of the randomized iterate. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol.\u00a04117, pp. 22\u201340. Springer, Heidelberg (2006)"},{"key":"45_CR7","unstructured":"Nisan, N.: \n                    \n                      \n                    \n                    $\\mathcal{RL}\\subset\\mathcal{SC}$\n                  . In: STOC 1992, pp. 619\u2013623. ACM (1992)"},{"key":"45_CR8","doi-asserted-by":"crossref","unstructured":"Nisan, N., Zuckerman, D.: More deterministic simulation in logspace. In: STOC 1993, pp. 235\u2013244. ACM (1993)","DOI":"10.1145\/167088.167162"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Raz, R., Reingold, O.: On recycling the randomness of states in space bounded computation. In: STOC 1999, pp. 159\u2013168 (1999)","DOI":"10.1145\/301250.301294"},{"issue":"1","key":"45_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","volume":"13","author":"G. Even","year":"1998","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Efficient approximation of product distributions. Random Struct. Algorithms\u00a013(1), 1\u201316 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"45_CR11","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200907","volume":"17","author":"N. Linial","year":"1997","unstructured":"Linial, N., Luby, M., Saks, M.E., Zuckerman, D.: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Combinatorica\u00a017(2), 215\u2013234 (1997)","journal-title":"Combinatorica"},{"key":"45_CR12","unstructured":"Armoni, R., Saks, M.E., Wigderson, A., Zhou, S.: Discrepancy sets and pseudorandom generators for combinatorial rectangles. In: FOCS 1996, pp. 412\u2013421 (1996)"},{"issue":"3","key":"45_CR13","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s004930200021","volume":"22","author":"C.J. Lu","year":"2002","unstructured":"Lu, C.J.: Improved pseudorandom generators for combinatorial rectangles. Combinatorica\u00a022(3), 417\u2013434 (2002)","journal-title":"Combinatorica"},{"issue":"4","key":"45_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O. Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM\u00a055(4), 17:1\u201317:24 (2008)","journal-title":"J. ACM"},{"key":"45_CR15","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom walks on regular digraphs and the \n                    \n                      \n                    \n                    $\\mathcal{RL}$\n                   vs. \n                    \n                      \n                    \n                    $\\mathcal{L}$\n                   problem. In: STOC 2006, pp. 457\u2013466. ACM (2006)","DOI":"10.1145\/1132516.1132583"},{"issue":"2","key":"45_CR16","first-page":"376","volume":"58","author":"M. Saks","year":"1999","unstructured":"Saks, M., Zhou, S.: BPHSPACE(S)\u2009\u2282\u2009DSPACE(S\n                  3\/2). J. CSS\u00a058(2), 376\u2013403 (1999)","journal-title":"J. CSS"},{"key":"45_CR17","unstructured":"Bogdanov, A., Dvir, Z., Verbin, E., Yehudayoff, A.: Pseudorandomness for width 2 branching programs. ECCC TR09-070 (2009)"},{"key":"45_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-27660-6_33","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"J. \u0160\u00edma","year":"2012","unstructured":"\u0160\u00edma, J., \u017d\u00e1k, S.: A sufficient condition for sets hitting the class of read-once branching programs of width 3. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol.\u00a07147, pp. 406\u2013418. Springer, Heidelberg (2012)"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A., Raz, R., Yehudayoff, A.: Pseudorandom generators for regular branching programs. In: FOCS 2010, pp. 40\u201347 (2010)","DOI":"10.1109\/FOCS.2010.11"},{"key":"45_CR20","doi-asserted-by":"crossref","unstructured":"Brody, J., Verbin, E.: The coin problem and pseudorandomness for branching programs. In: FOCS 2010, pp. 30\u201339 (2010)","DOI":"10.1109\/FOCS.2010.10"},{"key":"45_CR21","doi-asserted-by":"crossref","unstructured":"Kouck\u00fd, M., Nimbhorkar, P., Pudl\u00e1k, P.: Pseudorandom generators for group products. In: STOC 2011, pp. 263\u2013272. ACM (2011)","DOI":"10.1145\/1993636.1993672"},{"key":"45_CR22","doi-asserted-by":"crossref","unstructured":"De, A.: Pseudorandomness for permutation and regular branching programs. In: CCC 2011, pp. 221\u2013231 (2011)","DOI":"10.1109\/CCC.2011.23"},{"key":"45_CR23","unstructured":"Steinke, T.: Pseudorandomness for permutation branching programs without the group theory. ECCC TR12-083 (2012)"},{"key":"45_CR24","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: STOC 1994, pp. 356\u2013364 (1994)","DOI":"10.1145\/195058.195190"},{"key":"45_CR25","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Meka, R., Reingold, O., Trevisan, L., Vadhan, S.: Better pseudorandom generators from milder pseudorandom restrictions. In: FOCS 2012, pp. 120\u2013129 (2012)","DOI":"10.1109\/FOCS.2012.77"},{"key":"45_CR26","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput.\u00a022, 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"45_CR27","unstructured":"Tzur, Y.: Notions of weak pseudorandomness and GF(2n)-polynomials. Master\u2019s thesis, Weizmann Institute of Science (2009)"},{"key":"45_CR28","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Papakonstantinou, P.A., Wan, A.: Pseudorandomness for read-once formulas. In: FOCS 2011, pp. 240\u2013246 (2011)","DOI":"10.1109\/FOCS.2011.57"},{"key":"45_CR29","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Meka, R., Zuckerman, D.: Pseudorandomness from shrinkage. In: FOCS 2012, pp. 111\u2013119 (2012)","DOI":"10.1109\/FOCS.2012.78"},{"key":"45_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/11538462_37","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Rozenman","year":"2005","unstructured":"Rozenman, E., Vadhan, S.: Derandomized squaring of graphs. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX and RANDOM 2005. LNCS, vol.\u00a03624, pp. 436\u2013447. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:50:10Z","timestamp":1558302610000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}