One-tape turing machine and branching program lower bounds for MCSP. Cheraghchi, M., Hirahara, S., Myrisiotis, D., & Yoshida, Y. Theory of Computing Systems, Springer, 2022. Link Paper doi abstract bibtex For a size parameter $s:ℕ\toℕ$, the Minimum Circuit Size Problem (denoted by $MCSP[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f: \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A recent line of work exhibited ``hardness magnification'' phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant $μ_1 > 0$, if $MCSP[2^{μ_1· n}]$ cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time $N^{1.01}$, then $P\neq NP$. In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs: 1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute $MCSP[2^{μ_2· n}]$ in time $N^{1.99}$, for some constant $μ_2 > μ_1$. 2) A non-deterministic (or parity) branching program of size $o(N^{1.5}/łog N)$ cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola 2019). En route, we obtain several related results: 1)There exists a (local) hitting set generator with seed length $\widetilde{O}(\sqrt{N})$ secure against read-once polynomial-size non-deterministic branching programs on $N$-bit inputs. 2) Any read-once co-non-deterministic branching program computing MCSP must have size at least $2^{\widetilde{Ω}(N)}$.
@article{ref:CHMY22,
title={One-tape turing machine and branching program lower bounds for {MCSP}},
author={Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi},
journal={Theory of Computing Systems},
pages={1--32},
year={2022},
publisher={Springer},
doi = {10.1007/s00224-022-10113-9},
url_Link = {https://link.springer.com/article/10.1007/s00224-022-10113-9},
url_Paper = {https://eccc.weizmann.ac.il/report/2020/103/},
abstract = {For a size parameter
$s:\mathbb{N}\to\mathbb{N}$, the Minimum
Circuit Size Problem (denoted by $MCSP[s(n)]$)
is the problem of deciding whether the minimum
circuit size of a given function $f: \{0,1\}^n
\to \{0,1\}$ (represented by a string of length $N
:= 2^n$) is at most a threshold $s(n)$. A recent
line of work exhibited ``hardness magnification''
phenomena for MCSP: A very weak lower bound for MCSP
implies a breakthrough result in complexity theory.
For example, McKay, Murray, and Williams (STOC 2019)
implicitly showed that, for some constant $\mu_1 >
0$, if $MCSP[2^{\mu_1\cdot n}]$ cannot be
computed by a one-tape Turing machine (with an
additional one-way read-only input tape) running in
time $N^{1.01}$, then $P\neq NP$. In
this paper, we present the following new lower
bounds against one-tape Turing machines and
branching programs: 1) A randomized two-sided error
one-tape Turing machine (with an additional one-way
read-only input tape) cannot compute
$MCSP[2^{\mu_2\cdot n}]$ in time $N^{1.99}$, for
some constant $\mu_2 > \mu_1$. 2) A
non-deterministic (or parity) branching program of
size $o(N^{1.5}/\log N)$ cannot compute MKTP, which
is a time-bounded Kolmogorov complexity analogue of
MCSP. This is shown by directly applying the
Ne\v{c}iporuk method to MKTP, which previously
appeared to be difficult. These results are the
first non-trivial lower bounds for MCSP and MKTP
against one-tape Turing machines and
non-deterministic branching programs, and
essentially match the best-known lower bounds for
any explicit functions against these computational
models. The first result is based on recent
constructions of pseudorandom generators for
read-once oblivious branching programs (ROBPs) and
combinatorial rectangles (Forbes and Kelley, FOCS
2018; Viola 2019). En route, we obtain several
related results: 1)There exists a (local) hitting
set generator with seed length
$\widetilde{O}(\sqrt{N})$ secure against read-once
polynomial-size non-deterministic branching programs
on $N$-bit inputs. 2) Any read-once
co-non-deterministic branching program computing
MCSP must have size at least
$2^{\widetilde{\Omega}(N)}$. }
}
Downloads: 0
{"_id":"o2CpZdnKRjddR9FAH","bibbaseid":"cheraghchi-hirahara-myrisiotis-yoshida-onetapeturingmachineandbranchingprogramlowerboundsformcsp-2022","author_short":["Cheraghchi, M.","Hirahara, S.","Myrisiotis, D.","Yoshida, Y."],"bibdata":{"bibtype":"article","type":"article","title":"One-tape turing machine and branching program lower bounds for MCSP","author":[{"propositions":[],"lastnames":["Cheraghchi"],"firstnames":["Mahdi"],"suffixes":[]},{"propositions":[],"lastnames":["Hirahara"],"firstnames":["Shuichi"],"suffixes":[]},{"propositions":[],"lastnames":["Myrisiotis"],"firstnames":["Dimitrios"],"suffixes":[]},{"propositions":[],"lastnames":["Yoshida"],"firstnames":["Yuichi"],"suffixes":[]}],"journal":"Theory of Computing Systems","pages":"1–32","year":"2022","publisher":"Springer","doi":"10.1007/s00224-022-10113-9","url_link":"https://link.springer.com/article/10.1007/s00224-022-10113-9","url_paper":"https://eccc.weizmann.ac.il/report/2020/103/","abstract":"For a size parameter $s:ℕ\\toℕ$, the Minimum Circuit Size Problem (denoted by $MCSP[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f: \\{0,1\\}^n \\to \\{0,1\\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A recent line of work exhibited ``hardness magnification'' phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant $μ_1 > 0$, if $MCSP[2^{μ_1· n}]$ cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time $N^{1.01}$, then $P\\neq NP$. In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs: 1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute $MCSP[2^{μ_2· n}]$ in time $N^{1.99}$, for some constant $μ_2 > μ_1$. 2) A non-deterministic (or parity) branching program of size $o(N^{1.5}/łog N)$ cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola 2019). En route, we obtain several related results: 1)There exists a (local) hitting set generator with seed length $\\widetilde{O}(\\sqrt{N})$ secure against read-once polynomial-size non-deterministic branching programs on $N$-bit inputs. 2) Any read-once co-non-deterministic branching program computing MCSP must have size at least $2^{\\widetilde{Ω}(N)}$. ","bibtex":"@article{ref:CHMY22,\n title={One-tape turing machine and branching program lower bounds for {MCSP}},\n author={Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi},\n journal={Theory of Computing Systems},\n pages={1--32},\n year={2022},\n publisher={Springer},\n doi = {10.1007/s00224-022-10113-9},\n url_Link = {https://link.springer.com/article/10.1007/s00224-022-10113-9},\n url_Paper =\t {https://eccc.weizmann.ac.il/report/2020/103/},\n abstract =\t {For a size parameter\n $s:\\mathbb{N}\\to\\mathbb{N}$, the Minimum\n Circuit Size Problem (denoted by $MCSP[s(n)]$)\n is the problem of deciding whether the minimum\n circuit size of a given function $f: \\{0,1\\}^n\n \\to \\{0,1\\}$ (represented by a string of length $N\n := 2^n$) is at most a threshold $s(n)$. A recent\n line of work exhibited ``hardness magnification''\n phenomena for MCSP: A very weak lower bound for MCSP\n implies a breakthrough result in complexity theory.\n For example, McKay, Murray, and Williams (STOC 2019)\n implicitly showed that, for some constant $\\mu_1 >\n 0$, if $MCSP[2^{\\mu_1\\cdot n}]$ cannot be\n computed by a one-tape Turing machine (with an\n additional one-way read-only input tape) running in\n time $N^{1.01}$, then $P\\neq NP$. In\n this paper, we present the following new lower\n bounds against one-tape Turing machines and\n branching programs: 1) A randomized two-sided error\n one-tape Turing machine (with an additional one-way\n read-only input tape) cannot compute \n $MCSP[2^{\\mu_2\\cdot n}]$ in time $N^{1.99}$, for\n some constant $\\mu_2 > \\mu_1$. 2) A\n non-deterministic (or parity) branching program of\n size $o(N^{1.5}/\\log N)$ cannot compute MKTP, which\n is a time-bounded Kolmogorov complexity analogue of\n MCSP. This is shown by directly applying the\n Ne\\v{c}iporuk method to MKTP, which previously\n appeared to be difficult. These results are the\n first non-trivial lower bounds for MCSP and MKTP\n against one-tape Turing machines and\n non-deterministic branching programs, and\n essentially match the best-known lower bounds for\n any explicit functions against these computational\n models. The first result is based on recent\n constructions of pseudorandom generators for\n read-once oblivious branching programs (ROBPs) and\n combinatorial rectangles (Forbes and Kelley, FOCS\n 2018; Viola 2019). En route, we obtain several\n related results: 1)There exists a (local) hitting\n set generator with seed length\n $\\widetilde{O}(\\sqrt{N})$ secure against read-once\n polynomial-size non-deterministic branching programs\n on $N$-bit inputs. 2) Any read-once\n co-non-deterministic branching program computing\n MCSP must have size at least\n $2^{\\widetilde{\\Omega}(N)}$. }\n}\n\n","author_short":["Cheraghchi, M.","Hirahara, S.","Myrisiotis, D.","Yoshida, Y."],"key":"ref:CHMY22","id":"ref:CHMY22","bibbaseid":"cheraghchi-hirahara-myrisiotis-yoshida-onetapeturingmachineandbranchingprogramlowerboundsformcsp-2022","role":"author","urls":{" link":"https://link.springer.com/article/10.1007/s00224-022-10113-9"," paper":"https://eccc.weizmann.ac.il/report/2020/103/"},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"http://mahdi.ch/writings/cheraghchi.bib","dataSources":["YZqdBBx6FeYmvQE6D"],"keywords":[],"search_terms":["one","tape","turing","machine","branching","program","lower","bounds","mcsp","cheraghchi","hirahara","myrisiotis","yoshida"],"title":"One-tape turing machine and branching program lower bounds for MCSP","year":2022,"downloads":4}