For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{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 ${\rm 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 ${\rm P}\neq{\rm NP}$.

In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs:
\begin{enumerate}
\item A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute ${\rm MCSP}[2^{\mu_2\cdot n}]$ in time $N^{1.99}$, for some constant $\mu_2 > \mu_1$.
\item 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 Nechiporuk method to MKTP, which previously appeared to be difficult.
\end{enumerate}
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:
\begin{enumerate}
\item 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.
\item Any read-once co-non-deterministic branching program computing MCSP must have size at least $2^{\widetilde{\Omega}(N)}$.
\end{enumerate}

Added missing references; fixed typos.

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{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 ${\rm 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 ${\rm P}\neq{\rm NP}$.

In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs:
\begin{enumerate}
\item A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute ${\rm MCSP}[2^{\mu_2\cdot n}]$ in time $N^{1.99}$, for some constant $\mu_2 > \mu_1$.
\item 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 Nechiporuk method to MKTP, which previously appeared to be difficult.
\end{enumerate}
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:
\begin{enumerate}
\item 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.
\item Any read-once co-non-deterministic branching program computing MCSP must have size at least $2^{\widetilde{\Omega}(N)}$.
\end{enumerate}