{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:18:04Z","timestamp":1725549484772},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_28","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"336-347","source":"Crossref","is-referenced-by-count":4,"title":["Hardness Hypotheses, Derandomization, and Circuit Complexity"],"prefix":"10.1007","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","first-page":"1","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"E. Allender","year":"2001","unstructured":"Allender, E.: When the worlds collide: derandomization, lower bounds and kolmogorov complexity. In: Foundations of Software Technology and Theoretical Computer Science, pp. 1\u201315. Springer, Heidelberg (2001)"},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1109\/SFCS.1994.365713","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science","author":"E. Allender","year":"1994","unstructured":"Allender, E., Strauss, M.: Measure on small complexity classes with applications for BPP. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 807\u2013818. IEEE Computer Society, Los Alamitos (1994)"},{"key":"28_CR3","series-title":"Lecture Notes in Pure and Applied Mathematics","first-page":"1","volume-title":"Complexity, Logic and Recursion Theory","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies, K., Mayordomo, E.: Resource-bounded measure and randomness. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory. Lecture Notes in Pure and Applied Mathematics, pp. 1\u201347. Marcel Dekker, New York (1997)"},{"issue":"1","key":"28_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. Balc\u00e1zar","year":"1985","unstructured":"Balc\u00e1zar, J., Sch\u00f6ning, U.: Bi-immune sets for complexity classes. Mathematical Systems Theory\u00a018(1), 1\u201318 (1985)","journal-title":"Mathematical Systems Theory"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Cleve, R., Kannan, S., Gavalda, R., Tamon, C.: Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences\u00a052, 421\u2013433 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"28_CR6","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/S0890-5401(03)00119-6","volume":"186","author":"S. Fenner","year":"2003","unstructured":"Fenner, S., Fortnow, L., Naik, A., Rogers, J.: Inverting onto functions. Information and Computation\u00a0186(1), 90\u2013103 (2003)","journal-title":"Information and Computation"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1109\/CCC.2004.1313839","volume-title":"Proceedings of the 19th IEEE Conference on Computational Complexity","author":"C. Gla\u00dfer","year":"2004","unstructured":"Gla\u00dfer, C., Pavan, A., Selman, A.L., Sengupta, S.: Properties of NP-complete sets. In: Proceedings of the 19th IEEE Conference on Computational Complexity, pp. 184\u2013197. IEEE Computer Society, Los Alamitos (2004)"},{"issue":"11","key":"28_CR8","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s002360050109","volume":"34","author":"L.A. Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, L.A., Rothe, J., Wechsung, G.: Easy sets and hard certificate schemes. Acta Informatica\u00a034(11), 859\u2013879 (1997)","journal-title":"Acta Informatica"},{"key":"28_CR9","unstructured":"Hitchcock, J.M.: Small spans in scaled dimension. SIAM Journal on Computing.(to appear)"},{"issue":"1","key":"28_CR10","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1016\/S0304-3975(01)00340-1","volume":"289","author":"J.M. Hitchcock","year":"2002","unstructured":"Hitchcock, J.M.: MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theoretical Computer Science\u00a0289(1), 861\u2013869 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"28_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jcss.2003.09.001","volume":"69","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Scaled dimension and nonuniform complexity. Journal of Computer and System Sciences\u00a069(2), 97\u2013122 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R. Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences\u00a065, 672\u2013694 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR13","first-page":"43","volume-title":"Proceedings of the 18th IEEE Conference on Computational Complexity","author":"R. Impagliazzo","year":"2003","unstructured":"Impagliazzo, R., Moser, P.: A zero-one law for RP. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 43\u201347. IEEE Computer Society, Los Alamitos (2003)"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2001.1763","volume":"63","author":"V. Kabanets","year":"2001","unstructured":"Kabanets, V.: Easiness assumptions and hardness tests: Trading time for zero error. Journal of Computer and System Sciences\u00a063, 236\u2013252 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR16","first-page":"88","volume":"76","author":"V. Kabanets","year":"2002","unstructured":"Kabanets, V.: Derandomization: A brief overview. Bulletin of the EATCS\u00a076, 88\u2013103 (2002)","journal-title":"Bulletin of the EATCS"},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan, R.: Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control\u00a055, 40\u201356 (1982)","journal-title":"Information and Control"},{"key":"28_CR18","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 Journal on Computing\u00a031, 1501\u20131526 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"28_CR19","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1137\/S0097539795296206","volume":"28","author":"J. K\u00f6bler","year":"1998","unstructured":"K\u00f6bler, J., Watanabe, O.: New collapse consequences of NP having small circuits. SIAM Journal on Computing\u00a028(1), 311\u2013324 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"28_CR20","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s00037-001-8196-9","volume":"10","author":"C.-J. Lu","year":"2001","unstructured":"Lu, C.-J.: Derandomizing Arthur-Merlin games under uniform assumptions. Computational Complexity\u00a010(3), 247\u2013259 (2001)","journal-title":"Computational Complexity"},{"issue":"2","key":"28_CR21","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences\u00a044(2), 220\u2013258 (1992)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"28_CR22","first-page":"429","volume":"30","author":"J.H. Lutz","year":"1997","unstructured":"Lutz, J.H.: Observations on measure and lowness for\u00a0\n                    \n                      \n                    \n                    $\\Delta^{\\mathrm{P}}_2$\n                  . Theory of Computing Systems\u00a030(4), 429\u2013442 (1997)","journal-title":"Theory of Computing Systems"},{"key":"28_CR23","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-1-4612-1872-2_10","volume-title":"Complexity Theory Retrospective II","author":"J.H. Lutz","year":"1997","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 225\u2013260. Springer, New York (1997)"},{"issue":"4","key":"28_CR24","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J.H. Lutz","year":"1994","unstructured":"Lutz, J.H., Mayordomo, E.: Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing\u00a023(4), 762\u2013779 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR25","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(95)00189-1","volume":"164","author":"J.H. Lutz","year":"1996","unstructured":"Lutz, J.H., Mayordomo, E.: Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science\u00a0164, 141\u2013163 (1996)","journal-title":"Theoretical Computer Science"},{"key":"28_CR26","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1007\/978-1-4615-0013-1_19","volume-title":"Handbook of Randomized Computing","author":"P.B. Miltersen","year":"2001","unstructured":"Miltersen, P.B.: Derandomizing complexity classes. In: Handbook of Randomized Computing, vol.\u00a0II, pp. 843\u2013934. Kluwer, Dordrecht (2001)"},{"issue":"3","key":"28_CR27","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539701387039","volume":"31","author":"A. Pavan","year":"2002","unstructured":"Pavan, A., Selman, A.L.: Separation of NP-completeness notions. SIAM Journal on Computing\u00a031(3), 906\u2013918 (2002)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:58:50Z","timestamp":1605761930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}