{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T14:50:32Z","timestamp":1776955832610,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540407706","type":"print"},{"value":"9783540451983","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_18","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:32:30Z","timestamp":1294439550000},"page":"200-215","source":"Crossref","is-referenced-by-count":57,"title":["Computational Analogues of Entropy"],"prefix":"10.1007","author":[{"given":"Boaz","family":"Barak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronen","family":"Shaltiel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences\u00a028, 270\u2013299 (1984); Preliminary version in STOC 1982","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Theory and applications of trapdoor functions. In: 23rd FOCS, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing\u00a013, 850\u2013864 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing\u00a028, 1364\u20131396 (1999) (electronic)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR5","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C.E. Shannon","year":"1948","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal\u00a027, 379\u2013423, 623\u2013656 (1948)","journal-title":"Bell System Technical Journal"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/0220034","volume":"20","author":"A.V. Goldberg","year":"1991","unstructured":"Goldberg, A.V., Sipser, M.: Compression and ranking. SIAM Journal on Computing\u00a020, 524\u2013536 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01448847","volume":"100","author":"J. Neumann von","year":"1928","unstructured":"von Neumann, J.: Zur theorie der gesellschaftsspiele. Math. Ann.\u00a0100, 295\u2013320 (1928)","journal-title":"Math. Ann."},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A.R. Klivans","year":"2002","unstructured":"Klivans, A.R., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput.\u00a031, 1501\u20131526 (2002) (electronic)","journal-title":"SIAM J. Comput."},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. In: 40th FOCS, pp. 71\u201380 (1999)","DOI":"10.1109\/SFFCS.1999.814579"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudorandom generator. In: 42nd FOCS, pp. 648\u2013657 (2001)","DOI":"10.1109\/SFCS.2001.959941"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: 41st FOCS, pp. 32\u201342 (2000)","DOI":"10.1109\/SFCS.2000.892063"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Extracting randomness: How and why: A survey. In: Conference on Computational Complexity, pp. 44\u201358 (1996)","DOI":"10.1109\/CCC.1996.507667"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Nisan, T.-S.: Extracting randomness: A survey and new constructions. JCSS: Journal of Computer and System Sciences\u00a058 (1999)","DOI":"10.1006\/jcss.1997.1546"},{"key":"18_CR14","unstructured":"Shaltiel, R.: Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science 77, 67\u201395 (2002), Also available on, http:\/\/www.wisdom.weizmann.ac.il\/~ronens"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions. In: 21st STOC, pp. 12\u201324 (1989)","DOI":"10.1145\/73007.73009"},{"key":"#cr-split#-18_CR16.1","doi-asserted-by":"crossref","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. JCSS: Journal of Computer and System Sciences 62 (2001);","DOI":"10.1006\/jcss.2000.1730"},{"key":"#cr-split#-18_CR16.2","unstructured":"Preliminary version in STOC 1999. Also published as ECCC Report TR98-074"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Construction of extractors using pseudo-random generators. In: 31st STOC, pp. 141\u2013148 (1999)","DOI":"10.1145\/301250.301289"},{"key":"#cr-split#-18_CR18.1","doi-asserted-by":"crossref","unstructured":"Raz, R., Reingold, O., Vadhan, S.: Extracting all the randomness and reducing the error in trevisan???s extractors. JCSS: Journal of Computer and System Sciences 65 (2002);","DOI":"10.1006\/jcss.2002.1824"},{"key":"#cr-split#-18_CR18.2","unstructured":"Preliminary version in STOC 1999"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Extractors and pseudo-random generators with optimal seed length. In: ACM (ed.) 32nd STOC, pp. 1\u201310 (2000)","DOI":"10.1145\/335305.335306"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A., Zuckerman, D., Safra, S.: Extractors from Reed-Muller codes. In: IEEE (ed.) 42nd FOCS, pp. 638\u2013647 (2001)","DOI":"10.1109\/SFCS.2001.959940"},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity\u00a03, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: 29th STOC, 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness. J. Comput. System Sci.\u00a049, 149\u2013167 (1994)","journal-title":"J. Comput. System Sci."},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computations. In: ACM (ed.) 22nd STOC, pp. 204\u2013212 (1990)","DOI":"10.1145\/100216.100242"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: ACM (ed.) 26th STOC, pp. 356\u2013364 (1994)","DOI":"10.1145\/195058.195190"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Reingold, O., Shaltiel, R., Trevisan, L.: Streaming computation of combinatorial objects. In: Conference on Computational Complexity (CCC), vol.\u00a017 (2002)","DOI":"10.1109\/CCC.2002.1004352"},{"key":"18_CR27","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences\u00a052, 43\u201352 (1996); Preliminary version in STOC 1993","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR28","doi-asserted-by":"crossref","unstructured":"Saks, M.: Randomization and derandomization in space-bounded computation. In: Conference on Computational Complexity (CCC), pp. 128\u2013149 (1996)","DOI":"10.1109\/CCC.1996.507676"},{"key":"18_CR29","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science\u00a043, 169\u2013188 (1986)","journal-title":"Theoretical Computer Science"}],"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-540-45198-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:05:22Z","timestamp":1559916322000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}