{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:29Z","timestamp":1725728369736},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_15","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"174-182","source":"Crossref","is-referenced-by-count":1,"title":["Towards NEXP versus BPP?"],"prefix":"10.1007","author":[{"given":"Ryan","family":"Williams","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"15_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(99)00024-9","volume":"221","author":"A.E. Andreev","year":"1999","unstructured":"Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P.: Worst-case hardness suffices for derandomization: A new method for hardness-randomness tradeoffs. TCS: Theoretical Computer Science\u00a0221(1-2), 3\u201318 (1999)","journal-title":"TCS: Theoretical Computer Science"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"issue":"4","key":"15_CR3","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(4), 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"key":"15_CR4","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Short PCPs verifiable in polylogarithmic time. In: IEEE Conference on Computational Complexity, pp. 120\u2013134 (2005)"},{"issue":"2","key":"15_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00224-004-1194-y","volume":"38","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Fortnow, L., Pavan, A.: Some results on derandomization. Theory Comput. Syst.\u00a038(2), 211\u2013227 (2005)","journal-title":"Theory Comput. Syst."},{"key":"15_CR6","unstructured":"Goldreich, O., Wigderson, A.: On pseudorandomness with respect to deterministic observers. In: ICALP Satellite Workshops 2000, pp. 77\u201384 (2000)"},{"issue":"4","key":"15_CR7","first-page":"672","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. JCSS\u00a065(4), 672\u2013694 (2002)","journal-title":"JCSS"},{"key":"15_CR8","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 Annual ACM Symposium on the Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"1-2","key":"15_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity\u00a013(1-2), 1\u201346 (2004)","journal-title":"Computational Complexity"},{"issue":"2","key":"15_CR10","first-page":"149","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. JCSS\u00a049(2), 149\u2013167 (1994)","journal-title":"JCSS"},{"issue":"2","key":"15_CR11","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the xor lemma. Journal of Computer System Sciences\u00a062(2), 236\u2013266 (2001)","journal-title":"Journal of Computer System Sciences"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: ACM Symposium on Theory of Computing, pp. 231\u2013240 (2010)","DOI":"10.1145\/1806689.1806723"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. In: IEEE Conference on Computational Complexity, pp. 115\u2013125 (2011)","DOI":"10.1109\/CCC.2011.36"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Williams, R.: Natural proofs versus derandomization. In: ACM Symposium on Theory of Computing (to appear, 2013)","DOI":"10.1145\/2488608.2488612"},{"issue":"3","key":"15_CR15","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0304-3975(83)90015-4","volume":"26","author":"S. \u017d\u00e1k","year":"1983","unstructured":"\u017d\u00e1k, S.: A Turing machine time hierarchy. Theoretical Computer Science\u00a026(3), 327\u2013333 (1983)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T17:02:45Z","timestamp":1557766965000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}