{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T16:10:24Z","timestamp":1736525424274,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540380443"},{"type":"electronic","value":"9783540380450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_37","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T12:33:54Z","timestamp":1156509234000},"page":"398-409","source":"Crossref","is-referenced-by-count":1,"title":["Randomness-Efficient Sampling Within NC 1"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Healy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Ben-Or, M.: A theorem on probabilistic constant depth computation. In: Proceedings of STOC 1984, pp. 471\u2013474 (1984)","DOI":"10.1145\/800057.808715"},{"issue":"3","key":"37_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms\u00a03(3), 289\u2013304 (1992)","journal-title":"Random Structures & Algorithms"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Approximate counting with uniform constant-depth circuits. In: Advances in computational complexity theory, pp. 1\u201320. AMS (1993)","DOI":"10.1090\/dimacs\/013\/01"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Komlos, J., Szemeredi, E.: Deterministic simulation in LOGSPACE. In: Proceedings of STOC 1987, pp. 132\u2013140 (1987)","DOI":"10.1145\/28395.28410"},{"key":"37_CR5","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N. Alon","year":"1994","unstructured":"Alon, N., Roichman, Y.: Random cayley graphs and expanders. Random Structures & Algorithms\u00a05, 271\u2013284 (1994)","journal-title":"Random Structures & Algorithms"},{"issue":"3","key":"37_CR6","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.A.M. Barrington","year":"1990","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC 1. J. of Comp. & Sys. Sci.\u00a041(3), 274\u2013306 (1990)","journal-title":"J. of Comp. & Sys. Sci."},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Goldreich, O., Wigderson, A.: Deterministic amplification of space-bounded probabilistic algorithms. In: Proceedings of the 14th Conference on Computational Complexity, pp. 188\u2013198 (1999)","DOI":"10.1109\/CCC.1999.766276"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, A., Wigderson, A.: Dispersers, deterministic amplification, and weak random sources. In: Proceedings of FOCS 1989, pp. 14\u201319 (1989)","DOI":"10.1109\/SFCS.1989.63449"},{"key":"37_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/11672142_38","volume-title":"STACS 2006","author":"L. Fortnow","year":"2006","unstructured":"Fortnow, L., Klivans, A.: Linear advice for randomized logarithmic space. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 469\u2013476. Springer, Heidelberg (2006)"},{"issue":"1","key":"37_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M.L. Furst","year":"1984","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory\u00a017(1), 13\u201327 (1984)","journal-title":"Math. Systems Theory"},{"key":"37_CR11","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"Gabber, O., Galil, Z.: Explicit construction of linear size superconcentrators. Journal of Computer and System Sciences\u00a022, 407\u2013420 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Impagliazzo, R., Levin, L.A., Venkatesan, R., Zuckerman, D.: Security preserving amplification of hardness. In: Proceedings of FOCS 1990, pp. 318\u2013326 (1990)","DOI":"10.1109\/FSCS.1990.89550"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"Gillman, D.: A Chernoff bound for random walks on expander graphs. In: Proceedings of FOCS 1994, pp. 680\u2013691 (1994)","DOI":"10.1109\/SFCS.1993.366819"},{"key":"37_CR14","unstructured":"Goldreich, O.: A sample of samplers - a computational perspective on sampling. Elec. Colloquium on Computational Complexity 4(020) (1997)"},{"key":"37_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-12521-2","volume-title":"Modern cryptography, probabilistic proofs and pseudorandomness","author":"O. Goldreich","year":"1999","unstructured":"Goldreich, O.: Modern cryptography, probabilistic proofs and pseudorandomness. Springer, Berlin (1999)"},{"key":"37_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/978-3-540-27821-4_34","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Gutfreund","year":"2004","unstructured":"Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 381\u2013392. Springer, Heidelberg (2004)"},{"key":"37_CR17","unstructured":"Healy, A.: Randomness-efficient sampling within NC1. Elec. Col. on Comp. Complexity, TR06-058 (2006), http:\/\/eccc.hpi-web.de\/eccc\/"},{"key":"37_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/11672142_55","volume-title":"STACS 2006","author":"A. Healy","year":"2006","unstructured":"Healy, A., Viola, E.: Constant-depth circuits for arithmetic in finite fields of characteristic two. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 672\u2013683. Springer, Heidelberg (2006)"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: $\\mathit{P} = \\mathit{BPP}$ if E requires exponential circuits: Derandomizing the XOR lemma. In: Proc. of STOC 1997 (1997)","DOI":"10.1145\/258533.258590"},{"key":"37_CR20","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Zuckerman, D.: How to recycle random bits. In: Proceedings of FOCS 1989, pp. 248\u2013253 (1989)","DOI":"10.1109\/SFCS.1989.63486"},{"issue":"3","key":"37_CR21","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatroica\u00a08(3), 261\u2013277 (1988)","journal-title":"Combinatroica"},{"issue":"4","key":"37_CR22","first-page":"71","volume":"9","author":"G.A. Margulis","year":"1973","unstructured":"Margulis, G.A.: Explicit constructions of expanders. Problemy Peredachi Informatssi; Problems of Information Transmission\u00a09(4), 71\u201380 (1973)","journal-title":"Problemy Peredachi Informatssi; Problems of Information Transmission"},{"issue":"1","key":"37_CR23","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"},{"key":"37_CR24","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica\u00a012 (1992)","DOI":"10.1007\/BF01305237"},{"key":"37_CR25","doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. In: Proceedings of STOC 1990, pp. 213\u2013223 (1990)","DOI":"10.1145\/100216.100244"},{"issue":"4","key":"37_CR26","first-page":"598","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Akademiya Nauk SSSR. Mat. Zametki\u00a041(4), 598\u2013607, 623 (1987)","journal-title":"Akademiya Nauk SSSR. Mat. Zametki"},{"issue":"1","key":"37_CR27","doi-asserted-by":"publisher","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O. Reingold","year":"2002","unstructured":"Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product and new constant-degree expanders. Annals of Mathematics\u00a0155(1), 157\u2013187 (2002)","journal-title":"Annals of Mathematics"},{"key":"37_CR28","doi-asserted-by":"crossref","unstructured":"Saks, M.: Randomization and derandomization in space-bounded computation. In: Proc. of the 11th Conference on Computational Complexity (1996)","DOI":"10.1109\/CCC.1996.507676"},{"issue":"3-4","key":"37_CR29","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"E. Viola","year":"2004","unstructured":"Viola, E.: The complexity of constructing pseudorandom generators from hard functions. Computational Complexity\u00a013(3-4), 147\u2013188 (2004)","journal-title":"Computational Complexity"},{"key":"37_CR30","doi-asserted-by":"crossref","unstructured":"Viola, E.: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. In: Proc. of 20th Conf. on Comp. Complexity (2005)","DOI":"10.1109\/CCC.2005.25"},{"key":"37_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to circuit complexity","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to circuit complexity. Springer, Heidelberg (1999)"},{"key":"37_CR32","unstructured":"Wigderson, A., Xiao, D.: A randomness-efficient sampler for matrix-valued functions and applications. In: Proceedings of FOCS 2005 (2005). See also ECCC Technical Report TR05-107, http:\/\/eccc.hpi-web.de\/eccc\/"},{"issue":"4","key":"37_CR33","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","volume":"11","author":"D. Zuckerman","year":"1997","unstructured":"Zuckerman, D.: Randomness-optimal oblivious sampling. Random Structures & Algorithms\u00a011(4), 345\u2013367 (1997)","journal-title":"Random Structures & Algorithms"}],"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\/11830924_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T15:29:26Z","timestamp":1736522966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11830924_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}