{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:40:10Z","timestamp":1743824410961,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_38","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"447-458","source":"Crossref","is-referenced-by-count":3,"title":["Pseudorandomness for Linear Length Branching Programs and Stack Machines"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[]},{"given":"Periklis A.","family":"Papakonstantinou","sequence":"additional","affiliation":[]},{"given":"Andrew","family":"Wan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1145\/800057.808715","volume-title":"Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC 1984","author":"M. Ajtai","year":"1984","unstructured":"Ajtai, M., Ben-Or, M.: A theorem on probabilistic constant depth computations. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC 1984, pp. 471\u2013474. ACM, New York (1984)"},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 544\u2013553 (1990)","DOI":"10.1109\/FSCS.1990.89575"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: A non-linear time lower bound for boolean branching programs. In: 40th Annual Symposium on Foundations of Computer Science, pp. 60\u201370. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814578"},{"issue":"4","key":"38_CR4","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1145\/76359.76370","volume":"36","author":"E.W. Allender","year":"1989","unstructured":"Allender, E.W.: P-uniform circuit complexity. Journal of the ACM\u00a036(4), 912\u2013928 (1989)","journal-title":"Journal of the ACM"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Wigderson, A.: Deterministic simulation of probabilistic constant depth circuits. In: 26th Annual Symposium on Foundations of Computer Science, pp. 11\u201319. IEEE (1985)","DOI":"10.1109\/SFCS.1985.19"},{"issue":"3","key":"38_CR6","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"Borodin, A., Cook, S.A., Dymond, P.W., Ruzzo, W.L., Tompa, M.: Two applications of inductive counting for complementation problems. SIAM J. Comput\u00a018(3), 559\u2013578 (1989)","journal-title":"SIAM J. Comput"},{"issue":"4","key":"38_CR7","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1006\/jcss.2001.1778","volume":"63","author":"P. Beame","year":"2001","unstructured":"Beame, P., Jayram, T.S., Saks, M.: Time-space tradeoffs for branching programs. Journal of Computer and System Sciences\u00a063(4), 542\u2013572 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Papakonstantinou, P.A., Wan, A.: Pseudorandomness for read-once formulas. In: Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science, FOCS 2011 (2011)","DOI":"10.1109\/FOCS.2011.57"},{"issue":"5","key":"38_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1754399.1754401","volume":"57","author":"M. Braverman","year":"2010","unstructured":"Braverman, M.: Polylogarithmic independence fools AC 0 circuits. Journal of the ACM (JACM)\u00a057(5), 1\u201310 (2010)","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"38_CR10","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1145\/636865.636867","volume":"50","author":"P. Beame","year":"2003","unstructured":"Beame, P., Saks, M., Sun, X., Vee, E.: Time-space trade-off lower bounds for randomized computation of decision problems. Journal of the ACM (JACM)\u00a050(2), 154\u2013195 (2003)","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"38_CR11","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: Characterizations of pushdown machines in terms of time-bounded computers. Journal of ACM (JACM)\u00a018(1), 4\u201318 (1971)","journal-title":"Journal of ACM (JACM)"},{"key":"38_CR12","first-page":"522","volume-title":"Proceedings of Innovations in Computer Science - ICS 2010","author":"M. David","year":"2011","unstructured":"David, M., Nguyen, P., Papakonstantinou, P.A., Sidiropoulos, A.: Computationally limited randomness. In: Chazelle, B. (ed.) Proceedings of Innovations in Computer Science - ICS 2010, January 7-9, pp. 522\u2013536. Tsinghua University Press, Beijing (2011)"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"David, M., Papakonstantinou, P.A.: Trade-off lower bounds for stack machines. In: IEEE Conference on Computational Complexity (CCC), Boston, USA, pp. 163\u2013171 (2010)","DOI":"10.1109\/CCC.2010.23"},{"issue":"2","key":"38_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1561\/0400000007","volume":"2","author":"V. Guruswami","year":"2007","unstructured":"Guruswami, V.: Algorithmic results in list decoding. Foundations and Trends\u00ae in Theoretical Computer Science\u00a02(2), 107\u2013195 (2007)","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1145\/195058.195190","volume-title":"Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994","author":"R. Impagliazzo","year":"1994","unstructured":"Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994, Montr\u00e9al, Qu\u00e9bec, Canada, May 23-25, pp. 356\u2013364. ACM Press, New York (1994)"},{"issue":"1-2","key":"38_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity\u00a013(1-2), 1\u201346 (2004)","journal-title":"Computational Complexity"},{"issue":"1","key":"38_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"N. Nisan","year":"1991","unstructured":"Nisan, N.: Pseudorandom bits for constant depth circuits. Combinatorica\u00a011(1), 63\u201370 (1991)","journal-title":"Combinatorica"},{"issue":"4","key":"38_CR18","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica\u00a012(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"issue":"2","key":"38_CR19","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1006\/inco.1995.1064","volume":"118","author":"R. Niedermeier","year":"1995","unstructured":"Niedermeier, R., Rossmanith, P.: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits. Information and Computation\u00a0118(2), 227\u2013245 (1995)","journal-title":"Information and Computation"},{"issue":"2","key":"38_CR20","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. Journal of Computer Systems and Sciences (JCSS)\u00a021(2), 218\u2013235 (1980)","journal-title":"Journal of Computer Systems and Sciences (JCSS)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:25:16Z","timestamp":1743823516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}