{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:57:06Z","timestamp":1725544626416},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_38","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T08:27:54Z","timestamp":1141115274000},"page":"469-476","source":"Crossref","is-referenced-by-count":4,"title":["Linear Advice for Randomized Logarithmic Space"],"prefix":"10.1007","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam R.","family":"Klivans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","first-page":"75","volume-title":"Proceedings of the 19th IEEE Symposium on Foundations of Computer Science","author":"L. Adleman","year":"1978","unstructured":"Adleman, L.: Two theorems on random polynomial time. In: Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pp. 75\u201383. IEEE, New York (1978)"},{"key":"38_CR2","unstructured":"Allender, E., Barrington, D., Hesse, W.: Uniform circuits for division: Consequences and problems. In: Annual IEEE Conference on Computational Complexity, vol.\u00a016 (2001)"},{"key":"38_CR3","first-page":"188","volume-title":"Proceedings of the 14th IEEE Conference on Computational Complexity","author":"Z. Bar-Yossef","year":"1999","unstructured":"Bar-Yossef, Z., Goldreich, O., Wigderson, A.: Deterministic amplification of space-bounded probabilistic algorithms. In: Proceedings of the 14th IEEE Conference on Computational Complexity, pp. 188\u2013199. IEEE, New York (1999)"},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1051\/ita:2001119","volume":"35","author":"A. Chiu","year":"2001","unstructured":"Chiu, A., Davida, G., Litow, B.: Division in logspace-uniform NC1. RAIRO - Theoretical Informatics and Applications\u00a035, 259\u2013275 (2001)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1109\/SFCS.1989.63449","volume-title":"Proc. 30th Ann. IEEE Symp. on Foundations of Computer Science","author":"A. Cohen","year":"1989","unstructured":"Cohen, A., Wigderson, A.: Dispensers, deterministic amplification, and weak random sources (extended abstract). In: Proc. 30th Ann. IEEE Symp. on Foundations of Computer Science, Research Triangle Park, NC, oct, pp. 14\u201325. IEEE Computer Society Press, Los Alamitos (1989)"},{"issue":"3","key":"38_CR6","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 constructions of linear-sized superconcentrators. Journal of Computer and System Sciences\u00a022(3), 407\u2013420 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_17","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Wigderson, A.: Derandomization that is rarely wrong from short advice that is typically good. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, Springer, Heidelberg (2002)"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM) (2004)","DOI":"10.1007\/978-3-540-27821-4_34"},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1109\/SFCS.1989.63486","volume-title":"Proceedings of the 30th IEEE Symposium on Foundations of Computer Science","author":"R. Impagliazzo","year":"1989","unstructured":"Impagliazzo, R., Zuckerman, D.: How to recycle random bits. In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pp. 248\u2013253. IEEE, New York (1989)"},{"key":"38_CR10","first-page":"302","volume-title":"Proceedings of the 12th ACM Symposium on the Theory of Computing","author":"R. Karp","year":"1980","unstructured":"Karp, R., Lipton, R.: Some connections between nonuniform and uniform complexity classes. In: Proceedings of the 12th ACM Symposium on the Theory of Computing, pp. 302\u2013309. ACM, New York (1980)"},{"key":"38_CR11","unstructured":"Linial, N., Wigderson, A.: Lecture notes on expander graphs and their applications (2002), http:\/\/www.math.ias.edu\/~boaz\/ExpanderCourse\/index.html"},{"key":"38_CR12","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1997","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"38_CR13","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"},{"key":"38_CR14","volume-title":"Proceedings of the 36th ACM Symposium on the Theory of Computing","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings of the 36th ACM Symposium on the Theory of Computing, ACM Press, New York (2005)"},{"key":"38_CR15","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom walks in biregular graphs and the RL vs. L problem. Technical Report TR05-022, Electronic Colloquium on Computational Complexity (2005)","DOI":"10.1145\/1132516.1132583"},{"issue":"2","key":"38_CR16","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1006\/jcss.1998.1616","volume":"58","author":"M. Saks","year":"1999","unstructured":"Saks, M., Zhou, S.: BP H SPACE(S) \u2286 DPSPACE(S3\/2). Journal of Computer and System Sciences\u00a058(2), 376\u2013403 (1999)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T03:31:40Z","timestamp":1555471900000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11672142_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}