{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:56Z","timestamp":1740109376113,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2006455"],"award-info":[{"award-number":["CCF-2006455"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2107345"],"award-info":[{"award-number":["CCF-2107345"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s00224-022-10113-9","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T09:03:06Z","timestamp":1672131786000},"page":"868-899","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["One-Tape Turing Machine and Branching Program Lower Bounds for MCSP"],"prefix":"10.1007","volume":"68","author":[{"given":"Mahdi","family":"Cheraghchi","sequence":"first","affiliation":[]},{"given":"Shuichi","family":"Hirahara","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9585-1227","authenticated-orcid":false,"given":"Dimitrios","family":"Myrisiotis","sequence":"additional","affiliation":[]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,27]]},"reference":[{"issue":"6","key":"10113_CR1","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1137\/050628994","volume":"35","author":"E Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M, van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35(6), 1467\u20131493 (2006)","journal-title":"SIAM J. Comput."},{"key":"10113_CR2","unstructured":"Allender, E., Hirahara, S.: New insights on the (non-)hardness of circuit minimization and related problems. In: Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), pp 54:1\u201354:14 (2017)"},{"issue":"3","key":"10113_CR3","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/1706591.1706594","volume":"57","author":"E Allender","year":"2010","unstructured":"Allender, E., Kouck\u00fd, M.: Amplifying lower bounds by means of self-reducibility. J. ACM 57(3), 14:1\u201314:36 (2010)","journal-title":"J. ACM"},{"issue":"1","key":"10113_CR4","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jcss.2010.06.004","volume":"77","author":"E Allender","year":"2011","unstructured":"Allender, E., Kouck\u00fd, M, Ronneburger, D., Roy, S.: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77(1), 14\u201340 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"10113_CR5","doi-asserted-by":"crossref","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J, Peralta, R: Simple constructions of almost k-wise independent random variables. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS), pp 544\u2013553 (1990)","DOI":"10.1109\/FSCS.1990.89575"},{"key":"10113_CR6","doi-asserted-by":"crossref","unstructured":"Andreev, A.E., Baskakov, J.L., Clementi, A.E.F., Rolim, J.D.P.: Small pseudo-random sets yield hard functions: New tight explicit lower bounds for branching programs. In: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP), pp 179\u2013189 (1999)","DOI":"10.1007\/3-540-48523-6_15"},{"issue":"1","key":"10113_CR7","first-page":"5:1","volume":"9","author":"P Beame","year":"2016","unstructured":"Beame, P., Grosshans, N, McKenzie, P, Segoufin, L: Nondeterminism and an abstract formulation of Ne\u010diporuk\u2019s lower bound method. ACM Trans. Comput. Theory 9(1), 5:1\u20135:34 (2016)","journal-title":"ACM Trans. Comput. Theory"},{"key":"10113_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A.A., Smolensky, R.: On lower bounds for read-k-times branching programs. Comput. Complex. 3, 1\u201318 (1993)","journal-title":"Comput. Complex."},{"key":"10113_CR9","unstructured":"Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: Proceedings of the 31st Conference on Computational Complexity (CCC), pp 10:1\u201310:24 (2016)"},{"key":"10113_CR10","unstructured":"Chen, L., Hirahara, S., Oliveira, I.C., Pich, J., Rajgopal, N., Santhanam, R: Beyond natural proofs: Hardness magnification and locality. In: 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, pp 70:1\u201370:48 (2020)"},{"key":"10113_CR11","doi-asserted-by":"crossref","unstructured":"Chen, L., Ce, J., Ryan Williams, R.: Hardness magnification for all sparse NP languages. In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pp 1240\u20131255 (2019)","DOI":"10.1109\/FOCS.2019.00077"},{"key":"10113_CR12","unstructured":"Cheraghchi, M., Kabanets, V., Zhenjian, Lu, Myrisiotis, D.: Circuit lower bounds for MCSP from local pseudorandom generators. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, vol. 132 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fu\u0307r Informatik, pp 39:1\u201339:14 (2019)"},{"key":"10113_CR13","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Reckhow, R.A.: Time-bounded random access machines. In: Fischer, P.C., Paul Zeiger, H., Ullman, J.D., Rosenberg, A.L. (eds.) Proceedings of the 4th Annual ACM Symposium on Theory of Computing, May 1-3, 1972, Denver, Colorado, USA, pp 73\u201380. ACM (1972)","DOI":"10.1145\/800152.804898"},{"key":"10113_CR14","doi-asserted-by":"crossref","unstructured":"Forbes, M.A., Kelley, Z.: Pseudorandom generators for read-once branching programs, in any order. In: Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp 946\u2013955 (2018)","DOI":"10.1109\/FOCS.2018.00093"},{"issue":"5","key":"10113_CR15","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s10958-013-1350-5","volume":"191","author":"SB Gashkov","year":"2013","unstructured":"Gashkov, S.B., Sergeev, I.S.: Complexity of computation in finite fields. J. Math. Sci. 191(5), 661\u2013685 (2013)","journal-title":"J. Math. Sci."},{"key":"10113_CR16","unstructured":"Golovnev, A., Ilango, R, Impagliazzo, R, Kabanets, V., Kolokolova, A, Tal, A: AC0[p] lower bounds against MCSP via the coin problem. In: Baier, C, Chatzigiannakis, I, Flocchini, P, Leonardi, S (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, vol. 132 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 66:1\u201366:15 (2019)"},{"issue":"2","key":"10113_CR17","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1137\/17M1129088","volume":"47","author":"E Haramaty","year":"2018","unstructured":"Haramaty, E., Lee, C.H., Viola, E.: Bounded independence plus noise fools products. SIAM J. Comput. 47(2), 493\u2013523 (2018)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10113_CR18","doi-asserted-by":"publisher","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 pseudorandom generator from any one-way function. SIAM J. Comput. 28 (4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"10113_CR19","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"FC Hennie","year":"1965","unstructured":"Hennie, F.C.: One-tape off-line turing machine computations. Inf. Control 8(6), 553\u2013578 (1965)","journal-title":"Inf. Control"},{"key":"10113_CR20","doi-asserted-by":"crossref","unstructured":"Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp 247\u2013258 (2018)","DOI":"10.1109\/FOCS.2018.00032"},{"key":"10113_CR21","unstructured":"Hirahara, S.: Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. In: Saraf, S. (ed.) 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbr\u00fccken, Germany (Virtual Conference), vol. 169 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 20:1\u201320:47 (2020)"},{"key":"10113_CR22","unstructured":"Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: Proceedings of the 32nd Computational Complexity Conference (CCC), pp 7:1\u20137:20 (2017)"},{"key":"10113_CR23","unstructured":"Hirahara, S., Watanabe, O.: Limits of minimum circuit size problem as oracle. In: Proceedings of the 31st Conference on Computational Complexity (CCC), pp 18:1\u201318:20 (2016)"},{"key":"10113_CR24","unstructured":"Hitchcock, J.M., Pavan, A.: On the NP-completeness of the minimum circuit size problem. In: Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pp 236\u2013245 (2015)"},{"issue":"2","key":"10113_CR25","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/3230630","volume":"66","author":"R Impagliazzo","year":"2019","unstructured":"Impagliazzo, R., Meka, R., Zuckerman, D.: Pseudorandomness from Shrinkage. J. ACM 66(2), 11:1\u201311:16 (2019)","journal-title":"J. ACM"},{"key":"10113_CR26","volume-title":"Boolean Function Complexity - Advances and Frontiers, vol. 27 of Algorithms and combinatorics","author":"S Jukna","year":"2012","unstructured":"Jukna, S.: Boolean Function Complexity - Advances and Frontiers, vol. 27 of Algorithms and combinatorics. Springer, Berlin (2012)"},{"key":"10113_CR27","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Cai, J.-Y.: Circuit minimization problem. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp 73\u201379 (2000)","DOI":"10.1145\/335305.335314"},{"key":"10113_CR28","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Schnitger, G.: Communication complexity and lower bounds for sequential computation. In: Informatik, Festschrift zum 60. Geburtstag von G\u00fcnter Hotz, pp 253\u2013268. Teubner \/ Springer (1992)","DOI":"10.1007\/978-3-322-95233-2_15"},{"key":"10113_CR29","unstructured":"Lee, C.H.: Fourier bounds and pseudorandom generators for product tests. In: Proceedings of the 34th Computational Complexity Conference (CCC), pp 7:1\u20137:25 (2019)"},{"key":"10113_CR30","doi-asserted-by":"crossref","unstructured":"Maass, W: Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines (extended abstract). In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp 401\u2013408 (1984)","DOI":"10.1145\/800057.808706"},{"issue":"1","key":"10113_CR31","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/0216016","volume":"16","author":"W Maass","year":"1987","unstructured":"Maass, W., Schorr, A.: Speed-up of Turing machines with one work tape and a two-way input tape. SIAM J. Comput. 16(1), 195\u2013202 (1987)","journal-title":"SIAM J. Comput."},{"key":"10113_CR32","doi-asserted-by":"crossref","unstructured":"McKay, D.M., Murray, C.D., Ryan Williams, R.: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In: Proceedings of the Symposium on Theory of Computing (STOC), pp 1215\u20131225 (2019)","DOI":"10.1145\/3313276.3316396"},{"key":"10113_CR33","unstructured":"Murray, C.D., Williams, R.R.: On the (non) NP-hardness of computing circuit complexity. In: Proceedings of the 30th Conference on Computational Complexity (CCC), pp 365\u2013380 (2015)"},{"key":"10113_CR34","doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp 213\u2013223 (1990)","DOI":"10.1145\/100216.100244"},{"issue":"4","key":"10113_CR35","first-page":"765","volume":"169","author":"EI Ne\u010diporuk","year":"1966","unstructured":"Ne\u010diporuk, E.I.: On a Boolean function. Dokl. Akad. Nauk SSSR 169(4), 765\u2013766 (1966). English translation in Soviet Mathematics Doklady","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10113_CR36","unstructured":"Oliveira, I.C., Pich, J., Santhanam, R.: Hardness magnification near state-of-the-art lower bounds. In: Proceedings of the 34th Computational Complexity Conference (CCC), pp 27:1\u201327:29 (2019)"},{"key":"10113_CR37","doi-asserted-by":"crossref","unstructured":"Oliveira, I.C., Santhanam, R.: Hardness magnification for natural problems. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp 65\u201376 (2018)","DOI":"10.1109\/FOCS.2018.00016"},{"key":"10113_CR38","doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pp 204\u2013213 (1994)","DOI":"10.1145\/195058.195134"},{"key":"10113_CR39","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"CE Shannon","year":"1949","unstructured":"Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 28, 59\u201398 (1949)","journal-title":"Bell Syst. Tech. J."},{"issue":"1-3","key":"10113_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000010","volume":"7","author":"SP Vadhan","year":"2012","unstructured":"Vadhan, S.P.: Pseudorandomness. Found. Trends Theor. Comput. Sci. 7(1-3), 1\u2013336 (2012)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"10113_CR41","doi-asserted-by":"crossref","unstructured":"van Melkebeek, D, Raz, R: A time lower bound for satisfiability. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A, Sannella, D. (eds.) Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, vol. 3142 of Lecture Notes in Computer Science, pp 971\u2013982. Springer (2004)","DOI":"10.1007\/978-3-540-27836-8_81"},{"key":"10113_CR42","first-page":"51","volume":"26","author":"E Viola","year":"2019","unstructured":"Viola, E.: Pseudorandom bits and lower bounds for randomized Turing machines. Electron. Colloq. Comput. Complexity (ECCC) 26, 51 (2019)","journal-title":"Electron. Colloq. Comput. Complexity (ECCC)"},{"key":"10113_CR43","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(83)90133-0","volume":"24","author":"O Watanabe","year":"1983","unstructured":"Watanabe, O.: The time-precision tradeoff problem on on-line probabilistic Turing machines. Theor. Comput. Sci. 24, 105\u2013117 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10113-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10113-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10113-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T01:14:38Z","timestamp":1728609278000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10113-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,27]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10113"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10113-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,12,27]]},"assertion":[{"value":"17 November 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}