2026-07-22T18:26:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18880 2024-03-06T11:02:49Z ddc:004 open_access

Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE Cook, Joshua Moshkovitz, Dana MA PCP Circuit Complexity We prove that for some constant a > 1, for all k ≤ a, MATIME[n^{k+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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Cook and Dana Moshkovitz 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.55 urn:nbn:de:0030-drops-188805 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.55 eng https://creativecommons.org/licenses/by/4.0/legalcode