License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.55
URN: urn:nbn:de:0030-drops-188805
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18880/
Go to the corresponding LIPIcs Volume Portal

Cook, Joshua ; Moshkovitz, Dana

Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE

pdf-format:
LIPIcs-APPROX55.pdf (0.9 MB)

Abstract

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).

BibTeX - Entry

@InProceedings{cook_et_al:LIPIcs.APPROX/RANDOM.2023.55,
  author =	{Cook, Joshua and Moshkovitz, Dana},
  title =	{{Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{55:1--55:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18880},
  URN =		{urn:nbn:de:0030-drops-188805},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.55},
  annote =	{Keywords: MA, PCP, Circuit Complexity}
}

Keywords: MA, PCP, Circuit Complexity
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI