ECCC-Report TR22-014https://eccc.weizmann.ac.il/report/2022/014Comments and Revisions published for TR22-014en-usFri, 07 Jul 2023 21:18:47 +0300
Revision 2
| Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE |
Joshua Cook,
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2022/014#revision2We prove that 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 is a super linear polynomial circuit lower bound.
Previously, Santhanam showed that there exists a constant $c>1$ such that for all $k > 1$:
$$\mathbf{MATIME}[n^{c k}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})].$$
Inherently to Santhanam's proof, $c$ is a large constant and there is no upper bound on $c$. Using ideas from Murray and Williams, one can show for all $k > 1$:
$$\mathbf{MATIME}[n^{10 k^2}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})].$$
To prove this result, we construct the first $\mathbf{PCP}$ for $\mathbf{SPACE}[n]$ with quasi-linear verifier time: our $\mathbf{PCP}$ 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)]$ had verifiers that run in $\Omega(n^2)$ time. This $\mathbf{PCP}$ also proves that $\mathbf{NE}$ has $\mathbf{MIP}$ verifiers which run in time $\tilde{O}(n)$.Fri, 07 Jul 2023 21:18:47 +0300https://eccc.weizmann.ac.il/report/2022/014#revision2
Revision 1
| Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE |
Joshua Cook,
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2022/014#revision1We prove that 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. Previously, Santhanam showed that there exists a constant $c>1$ such that for all $k > 1$:
$$\mathbf{MATIME}[n^{c k}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})].$$
Inherently to Santhanam's proof, $c$ is a large constant and there is no upper bound on $c$. Using ideas from Murray and Williams, for 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}$ 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.Fri, 09 Sep 2022 02:55:39 +0300https://eccc.weizmann.ac.il/report/2022/014#revision1
Paper TR22-014
| Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE |
Joshua Cook,
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2022/014We 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.Tue, 08 Feb 2022 16:57:45 +0200https://eccc.weizmann.ac.il/report/2022/014