{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:23Z","timestamp":1760202623349},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"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-22006-7_48","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T03:44:05Z","timestamp":1308541445000},"page":"569-580","source":"Crossref","is-referenced-by-count":4,"title":["Robust Simulations and Significant Separations"],"prefix":"10.1007","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"48_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-45726-7_16","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"B. Barak","year":"2002","unstructured":"Barak, B.: A probabilistic-time hierarchy theorem for \u201cSlightly Non-uniform\u201d algorithms. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 194\u2013208. Springer, Heidelberg (2002)"},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01, 3\u201340 (1991)","journal-title":"Computational Complexity"},{"key":"48_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-02927-1_18","volume-title":"Automata, Languages and Programming","author":"H. Buhrman","year":"2009","unstructured":"Buhrman, H., Fortnow, L., Santhanam, R.: Unconditional lower bounds against advice. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 195\u2013209. Springer, Heidelberg (2009)"},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L., Thierauf, T.: Nonrelativizing separations. In: Proceedings of 13th Annual IEEE Conference on Computational Complexity, pp. 8\u201312 (1998)","DOI":"10.1109\/CCC.1998.694585"},{"key":"48_CR5","unstructured":"Cai, J.-Y.: S2 P\u2009\u2286\u2009ZPPNP. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 620\u2013629 (2001)"},{"key":"48_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S.: A hierarchy for nondeterministic time complexity. In: Fourth Annual ACM Symposium on Theory of Computing, Conference Record, Denver, Colorado, May 1-3, pp. 187\u2013192 (1972)","DOI":"10.1145\/800152.804913"},{"issue":"5","key":"48_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(88)90152-4","volume":"26","author":"S. Cook","year":"1988","unstructured":"Cook, S.: Short propositional formulas represent nondeterministic computations. Informations Processing Letters\u00a026(5), 269\u2013270 (1988)","journal-title":"Informations Processing Letters"},{"issue":"2","key":"48_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0304-3975(02)00810-1","volume":"298","author":"R. Downey","year":"2003","unstructured":"Downey, R., Fortnow, L.: Uniformly hard languages. Theoretical Computer Science\u00a0298(2), 303\u2013315 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"48_CR9","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1145\/1101821.1101822","volume":"52","author":"L. Fortnow","year":"2005","unstructured":"Fortnow, L., Lipton, R., van Melkebeek, D., Viglas, A.: Time-space lower bounds for satisfiability. Journal of the ACM\u00a052(6), 833\u2013865 (2005)","journal-title":"Journal of the ACM"},{"issue":"2","key":"48_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1006\/jcss.1999.1671","volume":"60","author":"L. Fortnow","year":"2000","unstructured":"Fortnow, L.: Time-space tradeoffs for satisfiability. Journal of Computer and System Sciences\u00a060(2), 337\u2013353 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polynomial time. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 316\u2013324 (2004)","DOI":"10.1109\/FOCS.2004.33"},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"issue":"4","key":"48_CR13","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(4), 672\u2013694 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"48_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 Annual ACM Symposium on the Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"2","key":"48_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(2), 236\u2013252 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"48_CR16","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(1), 40\u201356 (1982)","journal-title":"Information and Control"},{"issue":"2","key":"48_CR17","first-page":"191","volume":"28","author":"R. Karp","year":"1982","unstructured":"Karp, R., Lipton, R.: Turing machines that take advice. L\u2019Enseignement Math\u00e9matique\u00a028(2), 191\u2013209 (1982)","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"48_CR18","doi-asserted-by":"crossref","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 659\u2013667 (1999)","DOI":"10.1145\/301250.301428"},{"issue":"2","key":"48_CR19","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(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"48_CR20","first-page":"354","volume":"31","author":"A. Razborov","year":"1985","unstructured":"Razborov, A.: Lower bounds for the monotone complexity of some boolean functions. Soviet Mathematics Doklady\u00a031, 354\u2013357 (1985)","journal-title":"Soviet Mathematics Doklady"},{"issue":"1","key":"48_CR21","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A. Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055(1), 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"48_CR22","doi-asserted-by":"crossref","unstructured":"Santhanam, R.: Circuit lower bounds for Merlin-Arthur classes. In: Proceedings of 39th Annual Symposium on Theory of Computing, pp. 275\u2013283 (2007)","DOI":"10.1145\/1250790.1250832"},{"issue":"1","key":"48_CR23","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"Seiferas, J., Fischer, M., Meyer, A.: Separating nondeterministic time complexity classes. Journal of the ACM\u00a025(1), 146\u2013167 (1978)","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"48_CR24","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/j.tcs.2005.07.032","volume":"347","author":"V. Vinodchandran","year":"2005","unstructured":"Vinodchandran, V.: A note on the circuit complexity of PP. Theoretical Computer Science\u00a0347(1-2), 415\u2013418 (2005)","journal-title":"Theoretical Computer Science"},{"key":"48_CR25","doi-asserted-by":"crossref","unstructured":"van Melkebeek, D., Pervyshev, K.: A generic time hierarchy for semantic models with one bit of advice. In: Proceedings of 21st Annual IEEE Conference on Computational Complexity, pp. 129\u2013144 (2006)","DOI":"10.1109\/CCC.2006.7"},{"key":"48_CR26","doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pp. 231\u2013240 (2010)","DOI":"10.1145\/1806689.1806723"},{"key":"48_CR27","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds (2010) (manuscript)","DOI":"10.1109\/CCC.2011.36"},{"issue":"3","key":"48_CR28","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","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T21:48:08Z","timestamp":1560289688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}