{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:36:16Z","timestamp":1725600976419},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229527"},{"type":"electronic","value":"9783642229534"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22953-4_6","type":"book-chapter","created":{"date-parts":[[2011,8,17]],"date-time":"2011-08-17T08:28:08Z","timestamp":1313569688000},"page":"65-77","source":"Crossref","is-referenced-by-count":3,"title":["On the Optimal Compression of Sets in PSPACE"],"prefix":"10.1007","author":[{"given":"Marius","family":"Zimand","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","first-page":"303","volume-title":"Proceedings of the 24th Conference in Computational Complexity Conference","author":"L. Antunes","year":"2009","unstructured":"Antunes, L., Fortnow, L.: Worst-case running times for average-case algorithms. In: Proceedings of the 24th Conference in Computational Complexity Conference, pp. 303\u2013598. IEEE Computer Society Press, Los Alamitos (2009)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Antunes, L., Fortnow, L., Pinto, A., Souto, A.: Low-depth witnesses are easy to find. In: IEEE Conference on Computational Complexity, pp. 46\u201351 (2007)","DOI":"10.1109\/CCC.2007.13"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Approximate counting with uniform constant-depth circuits. In: Advances in computational complexity, pp. 1\u201320 (1993)","DOI":"10.1090\/dimacs\/013\/01"},{"issue":"3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1137\/S009753979834388X","volume":"31","author":"H. Buhrman","year":"2001","unstructured":"Buhrman, H., Fortnow, L., Laplante, S.: Resource-bounded Kolmogorov complexity revisited. SIAM J. Comput.\u00a031(3), 887\u2013905 (2001)","journal-title":"SIAM J. Comput."},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Laplante, S., Miltersen, P.B.: New bounds for the language compression problem. In: IEEE Conference on Computational Complexity, pp. 126\u2013130 (2000)","DOI":"10.1109\/CCC.2000.856742"},{"issue":"3","key":"6_CR6","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/s00037-005-0199-5","volume":"14","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Lee, T.: D van Melkebeek. Language compression and pseudorandom generators. Computational Complexity\u00a014(3), 228\u2013255 (2005)","journal-title":"Computational Complexity"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/11786986_30","volume-title":"Automata, Languages and Programming","author":"L. Fortnow","year":"2006","unstructured":"Fortnow, L., Hitchcock, J.M., Pavan, A., Vinodchandran, N.V., Wang, F.: Extracting Kolmogorov complexity with applications to dimension zero-one laws. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 335\u2013345. Springer, Heidelberg (2006)"},{"key":"6_CR8","unstructured":"Hitchcock, J.M., Pavan, A., Vinodchandran, N.V.: Kolmogorov complexity in randomness extraction. In: FSTTCS, pp. 215\u2013226 (2009)"},{"key":"6_CR9","first-page":"220","volume-title":"Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC 1997)","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC 1997), pp. 220\u2013229. Association for Computing Machinery, New York (1997)"},{"issue":"5","key":"6_CR10","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput.\u00a031(5), 1501\u20131526 (2002)","journal-title":"SIAM J. Comput."},{"issue":"2-3","key":"6_CR11","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.tcs.2005.07.017","volume":"345","author":"T. Lee","year":"2005","unstructured":"Lee, T., Romashchenko, A.E.: Resource bounded symmetry of information revisited. Theor. Comput. Sci.\u00a0345(2-3), 386\u2013405 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR12","volume-title":"Handbook on Randomized Computing","author":"P.B. Miltersen","year":"2001","unstructured":"Miltersen, P.B.: Derandomizing complexity classes. In: Pardalos, P., Reif, J., Rolim, J. (eds.) Handbook on Randomized Computing, vol.\u00a0II, Kluwer Academic Publishers, Dordrecht (2001)"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Musatov, D.: Improving the space-bounded version of Muchnik\u2019s conditional complexity theory via \u201cnaive\u201d derandomization. CoRR, abs\/1009.5108 (2010) (to appear in CSR 2011)","DOI":"10.1007\/978-3-642-20712-9_6"},{"key":"6_CR14","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. Journal of Computer and System Sciences\u00a049, 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the 15th ACM Symposium on Theory of Computing, pp. 330\u2013335 (1983)","DOI":"10.1145\/800061.808762"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pp. 32\u201342 (2000)","DOI":"10.1109\/SFCS.2000.892063"},{"key":"6_CR17","first-page":"175","volume":"17","author":"E. Viola","year":"2010","unstructured":"Viola, E.: Randomness buys depth for approximate counting. Electronic Colloquium on Computational Complexity (ECCC)\u00a017, 175 (2010)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"6_CR18","unstructured":"Zimand, M.: Possibilities and impossibilities in Kolmogorov complexity extraction. SIGACT News\u00a041(4) (December 2010)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Zimand, M.: Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov complexity. In: Proceedings 26th IEEE Conference on Computational Complexity (to appear, June 2011)","DOI":"10.1109\/CCC.2011.21"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22953-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T23:39:51Z","timestamp":1560469191000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22953-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229527","9783642229534"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22953-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}