One-tape Turing machine and branching program lower bounds for MCSP. Cheraghchi, M., Hirahara, S., Myrisiotis, D., & Yoshida, Y. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS), 2021. Invited to the special issue of Theory of Computing Systems.
One-tape Turing machine and branching program lower bounds for MCSP [link]Link  One-tape Turing machine and branching program lower bounds for MCSP [link]Paper  doi  abstract   bibtex   17 downloads  
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)}$.
@INPROCEEDINGS{ref:conf:CHMY21,
  author =	 {Mahdi Cheraghchi and Shuichi Hirahara and Dimitrios
                  Myrisiotis and Yuichi Yoshida},
  title =	 {One-tape Turing machine and branching program lower
                  bounds for {MCSP}},
  booktitle =	 {Proceedings of the 38th {International Symposium on
                  Theoretical Aspects of Computer Science (STACS)}},
  year =	 2021,
  keywords =	 {Minimum Circuit Size Problem, One-Tape Turing
                  Machines, Branching Programs, Lower Bounds,
                  Pseudorandom Generators, Hitting Set Generators},
  doi =		 {10.4230/LIPIcs.STACS.2021.23},
  url_Link = {https://drops.dagstuhl.de/opus/volltexte/2021/13668/},
  url_Paper =	 {https://eccc.weizmann.ac.il/report/2020/103/},
  note = {Invited to the special issue of Theory of Computing Systems.},
  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: 17
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021