%ACook, Joshua%AMoshkovitz, Dana%AMegow, Nicole Ed.%ASmith, Adam Ed.%D2024%ISchloss Dagstuhl – Leibniz-Zentrum für Informatik
%KMA; PCP; Circuit Complexity; Theory of computation → Complexity classes; Theory of computation → Circuit complexity; Theory of computation → Interactive proof systems
%MOSTI ID: 10498920
%PMedium: X
%TTighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE
%XWe prove that for some constant a > 1, for all k ≤ a, MATIME[n^{k(1+o(1))}]/1 ⊄ SIZE[O(n^k)], for some specific o(1) function. This is a super linear polynomial circuit lower bound.
Previously, Santhanam [Santhanam, 2007] showed that there exists a constant c>1 such that for all k>1: MATIME[n^{ck}]/1 ⊄ 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 [Murray and Williams, 2018], one can show for all k>1: MATIME [n^{10 k²}]/1 ⊄ SIZE[O(n^k)].
To prove this result, we construct the first PCP for SPACE[n] with quasi-linear verifier time: our PCP has a Õ(n) time verifier, Õ(n) space prover, O(log(n)) queries, and polynomial alphabet size. Prior to this work, PCPs for SPACE[O(n)] had verifiers that run in Ω(n²) time. This PCP also proves that NE has MIP verifiers which run in time Õ(n).
Country unknown/Code not availablehttps://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.55OSTI-MSA