TR22-014 Authors: Joshua Cook, Dana Moshkovitz

Publication: 8th February 2022 16:57

Downloads: 221

Keywords:

We prove for some constant $a > 1$, for all $k \leq a$,

$$\mathbf{MATIME}[n^{k + o(1)}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})],$$

for some specific $o(1)$ function. This improves on the Santhanam lower bound, which says there exists constant $c$ such that for all $k > 1$:

$$\mathbf{MATIME}[n^{c k}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})].$$

There is inherently no upper bound on $c$ in Santhanam's proof. Using ideas from Murray and Williams, all $k > 1$:

$$\mathbf{MATIME}[n^{10 k^2}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})].$$

Our proof uses a new, very efficient $\mathbf{PCP}$ for $\mathbf{PSPACE}$. We construct a $\mathbf{PCP}$ with unbounded proof length for $\mathbf{SPACE}[O(n)]$ that has a $\tilde{O}(n)$ time verifier, $\tilde{O}(n)$ space prover, $O(\log(n))$ queries, and polynomial alphabet size. Prior to this work, $\mathbf{PCP}$s for $\mathbf{SPACE}[O(n)]$ either used $\Omega(n)$ queries or had verifiers that run in $\Omega(n^2)$ time.