{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:01Z","timestamp":1750694701383},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,7,29]],"date-time":"2011-07-29T00:00:00Z","timestamp":1311897600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00224-011-9354-3","type":"journal-article","created":{"date-parts":[[2011,7,28]],"date-time":"2011-07-28T03:20:49Z","timestamp":1311823249000},"page":"179-195","source":"Crossref","is-referenced-by-count":3,"title":["On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography"],"prefix":"10.1007","volume":"51","author":[{"given":"Edward A.","family":"Hirsch","sequence":"first","affiliation":[]},{"given":"Dmitry","family":"Itsykson","sequence":"additional","affiliation":[]},{"given":"Ivan","family":"Monakhov","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Smal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,7,29]]},"reference":[{"key":"9354_CR1","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Pseudorandom generators in propositional proof complexity. Technical Report 00-023, Electronic Colloquium on Computational Complexity (2000). Extended abstract appears in Proceedings of FOCS-2000"},{"issue":"1","key":"9354_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000004","volume":"2","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: Average-case complexity. Found. Trends Theor. Comput. Sci. 2(1), 1\u2013106 (2006)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"4","key":"9354_CR3","doi-asserted-by":"crossref","first-page":"1353","DOI":"10.2178\/jsl\/1203350791","volume":"72","author":"S.A. Cook","year":"2007","unstructured":"Cook, S.A., Kraj\u00ed\u010dek, J.: Consequences of the provability of NP\u2286P\/poly. J. Symb. Log. 72(4), 1353\u20131371 (2007)","journal-title":"J. Symb. Log."},{"issue":"1","key":"9354_CR4","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. J. Symb. Log. 44(1), 36\u201350 (1979)","journal-title":"J. Symb. Log."},{"key":"9354_CR5","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1109\/FOCS.2004.33","volume-title":"Proceedings of the 45th IEEE Symposium on Foundations of Computer Science","author":"L. Fortnow","year":"2004","unstructured":"Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polynomial time. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp.\u00a0316\u2013324 (2004)"},{"issue":"3","key":"9354_CR6","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/1165555.1165565","volume":"37","author":"L. Fortnow","year":"2006","unstructured":"Fortnow, L., Santhanam, R.: Recent work on hierarchies for semantic classes. SIGACT News 37(3), 36\u201354 (2006)","journal-title":"SIGACT News"},{"issue":"1","key":"9354_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/GCC.2009.1","volume":"1","author":"D. Grigoriev","year":"2009","unstructured":"Grigoriev, D., Hirsch, E.A., Pervyshev, K.: A\u00a0complete public-key cryptosystem. Groups, Complexity, Cryptology 1(1), 1\u201312 (2009)","journal-title":"Groups, Complexity, Cryptology"},{"issue":"3","key":"9354_CR8","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1090\/S1061-0022-10-01103-9","volume":"21","author":"E.A. Hirsch","year":"2010","unstructured":"Hirsch, E.A., Itsykson, D.M.: An infinitely-often one-way function based on an average-case assumption. St. Petersburg Math. J. 21(3), 459\u2013468 (2010)","journal-title":"St. Petersburg Math. J."},{"issue":"4","key":"9354_CR9","doi-asserted-by":"crossref","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\u00a0pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"9354_CR10","volume-title":"Proc. of EUROCRYPT-2005","author":"D. Harnik","year":"2005","unstructured":"Harnik, D., Kilian, J., Naor, M., Reingold, O., Rosen, A.: On robust combiners for oblivious transfer and other primitives. In: Proc. of EUROCRYPT-2005 (2005)"},{"issue":"3","key":"9354_CR11","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.apal.2010.09.006","volume":"162","author":"D.M. Itsykson","year":"2010","unstructured":"Itsykson, D.M.: Structural complexity of AvgBPP. Ann. Pure Appl. Log. 162(3), 213\u2013223 (2010)","journal-title":"Ann. Pure Appl. Log."},{"issue":"3","key":"9354_CR12","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.2307\/2274765","volume":"54","author":"J. Kraj\u00ed\u010dek","year":"1989","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations. J. Symb. Log. 54(3), 1063\u20131079 (1989)","journal-title":"J. Symb. Log."},{"issue":"1\u20133","key":"9354_CR13","doi-asserted-by":"crossref","first-page":"123","DOI":"10.4064\/fm170-1-8","volume":"170","author":"J. Kraj\u00ed\u010dek","year":"2001","unstructured":"Kraj\u00ed\u010dek, J.: On the weak pigeonhole principle. Fundam. Math. 170(1\u20133), 123\u2013140 (2001)","journal-title":"Fundam. Math."},{"issue":"2","key":"9354_CR14","doi-asserted-by":"crossref","first-page":"197","DOI":"10.2307\/2687774","volume":"7","author":"J. Kraj\u00ed\u010dek","year":"2001","unstructured":"Kraj\u00ed\u010dek, J.: Tautologies from pseudorandom generators. Bull. Symb. Log. 7(2), 197\u2013212 (2001)","journal-title":"Bull. Symb. Log."},{"key":"9354_CR15","first-page":"265","volume":"9","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A.: Universal sequential search problems. Probl. Inf. Transm. 9, 265\u2013266 (1973)","journal-title":"Probl. Inf. Transm."},{"key":"9354_CR16","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"L.A. Levin","year":"1987","unstructured":"Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7, 357\u2013363 (1987)","journal-title":"Combinatorica"},{"key":"9354_CR17","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-662-12788-9_6","volume-title":"Concentration","author":"C. McDiarmid","year":"1998","unstructured":"McDiarmid, C.: In: Concentration. Algorithms and Combinatorics, vol.\u00a016, pp.\u00a0195\u2013248. Springer, Berlin (1998)"},{"key":"9354_CR18","series-title":"Lecture Notes in Computer Science","first-page":"361","volume-title":"Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science","author":"J. Messner","year":"1999","unstructured":"Messner, J.: On optimal algorithms and optimal proof systems. In: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol.\u00a01563, pp.\u00a0361\u2013372 (1999)"},{"issue":"4\u20135","key":"9354_CR19","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/j.tcs.2010.09.029","volume":"412","author":"H. Monroe","year":"2011","unstructured":"Monroe, H.: Speedup for natural problems and noncomputability. Theor. Comput. Sci. 412(4\u20135), 478\u2013481 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9354_CR20","first-page":"347","volume-title":"Proceedings of the 22nd IEEE Conference on Computational Complexity","author":"K. Pervyshev","year":"2007","unstructured":"Pervyshev, K.: On heuristic time hierarchies. In: Proceedings of the 22nd IEEE Conference on Computational Complexity, pp.\u00a0347\u2013358 (2007)"},{"issue":"1\u20133","key":"9354_CR21","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(02)00411-5","volume":"295","author":"P. Pudl\u00e1k","year":"2003","unstructured":"Pudl\u00e1k, P.: On reducibility and symmetry of disjoint NP pairs. Theor. Comput. Sci. 295(1\u20133), 323\u2013339 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9354_CR22","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: On provably disjoint NP-pairs. Technical Report 94-006, Electronic Colloquium on Computational Complexity (1994)","DOI":"10.7146\/brics.v1i36.21607"},{"key":"9354_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/10703163_13","volume-title":"Proceedings of CSL\u201998","author":"Z. Sadowski","year":"1999","unstructured":"Sadowski, Z.: On an optimal deterministic algorithm for SAT. In: Proceedings of CSL\u201998. Lecture Notes in Computer Science, vol.\u00a01584, pp.\u00a0179\u2013187. Springer, Berlin (1999)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9354-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9354-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9354-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T09:55:39Z","timestamp":1560419739000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9354-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,29]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9354"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9354-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,29]]}}}