<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE</title></titleStmt>
			<publicationStmt>
				<publisher>Schloss Dagstuhl – Leibniz-Zentrum für Informatik</publisher>
				<date>09/04/2024</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10498920</idno>
					<idno type="doi">10.4230/LIPIcs.APPROX/RANDOM.2023.55</idno>
					<title level='j'>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)</title>
<idno></idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Joshua Cook</author><author>Dana Moshkovitz</author><author>Nicole Megow</author><author>Adam Smith</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[We 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 Õ(n) time verifier, Õ(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 Õ(n).]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>Some of the most fundamental problems in complexity theory are proving circuit lower bounds for uniform complexity classes. One such conjecture is that NP does not have polynomial size circuits, which is a strong version of P &#824; = NP. Very little is known on such lower bounds. In particular, there are no known proofs that NEXP does not have polynomial sized circuits! However, there are some closely related results that could be loosely seen as relaxations.</p><p>One can strengthen NP slightly by giving the non-deterministic algorithm access to randomness, as well as an extra bit of trusted advice. This gives the complexity class MA/1. We can weaken polynomial sized circuits to circuits of fixed polynomial size: SIZE[n k ] for constant k.</p><p>To get our fine grained results, we need a PCP for space S = O(n) and time T = 2 O(n)  algorithms, where the verifier simultaneously has &#213;(n) time and poly(log(n)) many queries. Further, the PCP needs a prover that can compute any bit of the proof in &#213;(n) space. Notably, we do not need any bounds on the proof length.</p><p>The PCP given by Babai, Fortnow, and Lund in their proof that MIP = NEXP <ref type="bibr">[4]</ref> required &#8486;(log(T )) queries, while we want O(log(log(T ))) queries.</p><p>Holmgren and Rothblum in their work on delegated computation <ref type="bibr">[20]</ref> improved on the BFL PCP in several ways that can<ref type="foot">foot_0</ref> be used to give a PCP with verifier time &#213;(n + log(T )). Unfortunately, it still requires &#8486;(log(T )) queries.</p><p>Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan <ref type="bibr">[5]</ref> gave a PCP that uses a constant number of queries, but has verifier time poly(log(T )), while we need &#213;(n + log(T )) verifier time. Similar results were given by subsequent work <ref type="bibr">[23,</ref><ref type="bibr">8,</ref><ref type="bibr">6]</ref>.</p><p>The small space requirement for the prover is achieved by Holmgren and Rothblum <ref type="bibr">[20]</ref>. In some PCPs, like the PCP in Ben-Sasson, Chiesa, Genkin, and Tromer's work on the concrete efficiency of PCPs <ref type="bibr">[6]</ref>, the prover requires space &#8486;(T ). In contrast, our result needs prover space &#213;(S + n).</p><p>A sufficiently efficient PCP was not known, so we construct a new PCP.</p><p>&#9654; Theorem 3 (Verifier Efficient PCP). Let S, T = &#8486;(n) be functions, and L be any language computed by a simultaneous time T and space S algorithm. Let &#948; &#8712; (0, 1/2) be a constant. Then there is a PCP for L with:</p><p>1. Verifier time &#213;(n + log(T )).</p><p>2. Query time &#213;(log(T )).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">O(log(n)</head><p>+ log(log(T ))) queries. 4. Alphabet &#931; with log(|&#931;|) = O(log(log(T ))).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>5.</head><p>Log of proof length &#213;(log(T )). 6. Prover space &#213;(S).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.">Perfect completeness and soundness &#948;.</head><p>We believe we can achieve a similar verifier time, query time and prover space while also achieving constant number of queries and alphabet size. We do not need these improvements for our main result, so we only prove this simpler result.</p><p>Only our prover requires the space bound for its efficient computation. If we remove this space limitation, we get a similar PCP for nondeterministic algorithms.</p><p>&#9654; Theorem 4 (Verifier Efficient PCP for Nondeterministic Algorithms). Let T = &#8486;(n), &#948; &#8712; (0, 1/2) be a constant, and L &#8712; NTIME[T ]. Then there is a PCP for L with: 1. Verifier time &#213;(n + log(T )).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Query time &#213;(log(T )).</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">O(log(n) + log(log(T ))) queries. 4. Alphabet &#931; with log(|&#931;|) = O(log(log(T ))).</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.">Log of proof length &#213;(log(T )).</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6.">Perfect completeness and soundness &#948;.</head><p>An immediate corollary of Theorem 4 is a more fine grained equivalence between MIP and NEXP.</p><p>&#9654; Corollary 5 (Fine Grained Equivalence of MIP = NEXP). For any time constructable function p(n) = &#8486;(n), language L &#8712; NTIME[2 &#213;(p(n)) ] if and only if there is a two prover, one round MIP protocol for L whose verifier runs in time &#213;(p(n)).</p><p>Note this equivalence implies a hierarchy theorem for MIP since there are hierarchy theorems for NTIME <ref type="bibr">[11,</ref><ref type="bibr">30,</ref><ref type="bibr">34,</ref><ref type="bibr">15]</ref>.</p><p>A special case is MIP protocols for NE.</p><p>&#9654; Corollary 6 (NE Has Quasi-linear Time Verifiers). For any language L &#8712; NE, there is a two prover, one round MIP protocol for L whose verifier runs in time &#213;(n). Note this verifier time is nearly optimal since the verifier requires linear time to read its entire input. All previous PCPs fail to achieve such an efficient MIP verifier. If the original PCP makes &#8486;(n) queries of size &#8486;(n), then it takes &#8486;(n 2 ) time to send the queries even if we allow more provers. And all previous PCPs with fewer queries require verifier time &#8486;(n 2 ) to either verify the response or compute the queries.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.2">Proof Idea</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.2.1">MA Lower Bounds Using PCP</head><p>We first review Santhanam's original proof.</p><p>Santhanam's original result uses the fact that if PSPACE &#8834; P/poly, then PSPACE = MA. This follows from the famous result that IP = PSPACE <ref type="bibr">[31,</ref><ref type="bibr">22]</ref>. The idea is that if PSPACE &#8834; P/poly, then an MA protocol can guess a circuit computing any problem in PSPACE. The prover in the interactive protocol for PSPACE is also computable in PSPACE. So to solve any PSPACE problem in MA, the MA protocol first guesses the circuit for a prover, then simulates the verifier using the circuit we guessed as the prover.</p><p>Using this, Santhanam's original proof then considered two cases: either PSPACE &#8834; P/poly, or PSPACE &#824; &#8834; P/poly.</p><p>If PSPACE &#8834; P/poly, then we already know PSPACE = MA. Now we just need a problem not computable by a size n k circuit. But there is a straightforward algorithm that exhaustively finds a circuit of size larger than n k that computes a function that cannot be computed by a smaller circuit. In fact, such an algorithm only requires space &#213;(n k ). So</p><p>If PSPACE &#824; &#8834; P/poly, then we know a hard problem that is not in SIZE[n k ], namely any PSPACE complete problem. Let us take a PSPACE complete, downward self reducible language, Y . Now Y may be too hard for MA to solve, but if we give it enough padding, eventually the padded version of Y will be computable by size n k circuits. But for this amount of padding, MA can pull the same trick it does in the PSPACE &#8834; P/poly case. Namely, guess a circuit for Y and then simulate the IP protocol for Y . For some PSPACE complete Y , the language itself is its proof and this works. The trick is to use just the right amount of padding so it requires circuits of at least size n k , but not much larger. Santhanam uses the single bit of advice in a clever way to figure out when there is just the right amount of padding.</p><p>In either case, the time of this protocol is roughly the time of the verifier in the IP protocol, plus the size of the prover circuit times the number of times the prover is queried.</p><p>There are two reasons the MA protocol could take polynomially more time than the size of the circuits it wants to compute in the case PSPACE &#8834; P/poly. One is that the IP from the original Santhanam result has polynomial verifier time and a polynomial time interaction with the prover, making the verifier in the MA/1 protocol take polynomially longer than the circuit complexity of the problem being solved. By using a PCP, we get better results. The other is that the prover circuit complexity could be large, depending on the circuit size required for PSPACE (could be any polynomial when PSPACE &#8834; P/poly). This is the reason there is no upper bound on the polynomial run time of the MA/1 protocol in Santhanam's proof. To avoid this issue we consider a finer case analysis.</p><p>We break the problem into three cases. For some SPACE[O(n)] complete language, X, we have one<ref type="foot">foot_1</ref> of the following: 1. X / &#8712; P/poly. 2. X &#8712; SIZE[n 1+o (1) ]. (1) ] \ SIZE[n a-o (1) ] for some a &gt; 1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">X &#8712; SIZE[n a+o</head><p>The original proof only used the two cases X / &#8712; P/poly and X &#8712; P/poly. The case where X / &#8712; P/poly is completely unchanged. Note that this is the plausible case, and here there is no constant upper bound a on k.</p><p>If X &#8712; P/poly, we use our efficient PCP, Theorem 3, instead of the IP Santhanam uses. With this substitution, the case where X &#8712; SIZE[n 1+o (1) ] is almost unchanged from the original proof. By separating this into it's own case, we get tight bounds for all k in this case.</p><p>If X &#8712; SIZE[n a+o (1) ] \ SIZE[n a-o (1) ] for some a &gt; 1, then we use the same padding technique we use if X / &#8712; P/poly, just using our new PCP. In this case, we can only do this if for some k &lt; a, we are trying to show MATIME[n k+o (1) ]/1 &#824; &#8834; SIZE[n k-o (1) ]. This is the case where a is finite, but in this case, we can use Santhanam's argument using our PCP to get Theorem 2.</p><p>To see why k &gt; a poses a difficulty, suppose</p><p>Then to get a language requiring size n 3 circuits, we need to use a space n 3 algorithm. But the prover for a space n 3 language is a language running on an input with length n 3 , and using space linear in its input length. Thus we may need a size (n 3 ) 2 = n 6 circuit for our prover. So the verifier takes time at least n 6 to even read the prover circuit, thus can't run in time n 3 . See Item 2 in our open problems for further explanation. &#9654; Remark 7. We note our verifier in Theorem 1 is a RAM machine, not a standard Turing Machine. This is because we know how to efficiently simulate a circuit on a RAM machine, but not on a standard Turing Machine.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.2.2">Verifier Efficient PCP</head><p>Now we explain the PCP we actually use in the MA protocol. We start with a PCP similar to <ref type="bibr">[20]</ref> and <ref type="bibr">[4]</ref> that we refer to as our base PCP. This PCP has a verifier that runs in time &#213;(n + log(T )) and uses O(log(T )) queries. To reduce the number of queries, we use PCP composition <ref type="bibr">[3,</ref><ref type="bibr">7,</ref><ref type="bibr">13,</ref><ref type="bibr">25,</ref><ref type="bibr">12]</ref>.</p><p>To perform PCP composition, we need a robust PCP. Loosely, a robust PCP is a PCP so that when x / &#8712; L, for any proof, most sets of queries to that proof return not only a rejected response, but a response that is far from any accepted response. To make our base PCP robust, we use the aggregation through curves technique <ref type="bibr">[2]</ref>. Now we briefly explain how to use aggregation through curves to convert our base PCP into a robust PCP.</p><p>An honest proof for our base PCP is a single low degree polynomial. Suppose our base PCP has q queries. To make our PCP robust, we first choose the randomness for the base PCP, and another random point in the PCP proof. Then we find the degree q curve that goes through all these points. Then we check if the proof, restricted to this curve, is a low degree polynomial, and whether the base PCP would have accepted on this input. Since a low degree polynomial is an error correcting code, this gives robustness.</p><p>One concern one might have with this robust PCP is that it actually requires &#8486;(log(T ) 2 ) queries. We don't need to actually calculate all of these query locations. Since we reduce the actual number of queries with PCP composition, we only need to be able to calculate any individual query location quickly. To find these query locations requires us to compute a point on the degree q curve going through each of our q points our base PCP queries plus a random point. In our base PCP, q = O(log(T )) and our proof has dimension O(log(T )). So the naive way to compute this curve is to calculate each coordinate independently, which would take time &#213;(log(T ) 2 ).</p><p>To efficiently compute low degree curves through points, or to extrapolate a function going through those points, we introduce the concept of time extrapolatable functions.</p><p>&#9654; Definition 8 (Extrapolatability). For any n, q, t &gt; 0, and field F, we call Q : [q] &#8594; F n "t extrapolatable" (or time t extrapolatable) if there is a time t algorithm taking any v &#8712; F q , that outputs</p><p>Equivalently, if we think of Q as outputting the columns of a matrix, then we say Q is time t extrapolatable if one can multiply a vector with it in time t. An important property of extrapolatable functions is that an extrapolation of an extrapolatable function can be computed efficiently. This is where it gets its name.</p><p>Our base PCP is just a sum check and a few point checks. Each of these are time &#213;(log(T )) extrapolatable. Our robust PCP only queries locations easily computable given the extrapolation of our base PCP query locations. Extrapolations of extrapolatable functions are easy to compute, so we can easily compute the query locations of the robust PCP.</p><p>We also introduce the concept an extrapolatable PCP (ePCP) as one where an honest proof is a low degree polynomial, and the query locations after fixing a choice of randomness are extrapolatable. We show that any ePCP can be extended into a robust PCP where the query locations of that robust PCP can be computed efficiently.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.3">Generalization And Sharpness</head><p>We actually prove a stronger result than Theorem 1 that is sharp. First, our MA protocol is input oblivious: the message from Merlin is just a program for computing a PSPACE complete language and doesn't depend on the specific input, just its length. Second, the hardness is against the model used in Merlin's message. We used circuits, but we can describe a randomized algorithm directly to save some polynomial factors.</p><p>We define input oblivious Merlin-Arthur time, OMATIME, the same way as Fortnow, Santhanam, and Williams <ref type="bibr">[17]</ref>. Input oblivious Merlin-Arthur are languages solvable with untrusted advice, where the advice only depends on the input length. In our case, Merlin gets to send a long, untrusted message for every input length, and Arthur also gets a single bit of trusted advice. Note that Santhanam's original proof implicitly also uses input oblivious MA.</p><p>The main property of circuits we use is that a randomized algorithm can efficiently simulate it. We can instead use BPTIME[n k ]/n k , that is, randomized algorithms running in time n k with description length n k . This uses the same model of computation as our verifier, allowing it to more efficiently simulate OMATIME.</p><p>Using OMATIME instead of MATIME and BPTIME instead of SIZE, we can follow the same proof as our main result to show: &#9654; Theorem 9 (OMATIME Lower Bound Against BPTIME). There exists constant a &gt; 1, such that for all k &lt; a, for some</p><p>This result is tight in the sense that for any function f (n), we have</p><p>To get stronger results, we need to use nondeterminism that depends on the input. So one could say our result is less about the power of nondeterminism, and more about the power of trusted versus untrusted advice. Specifically: trusting advice doesn't always buy (much) time in the randomized setting, as long as we have some trusted advice.</p><p>Let us briefly outline what would need to change in our main proof to prove Theorem 9, and justify why those changes would work.</p><p>First we need to make a class of randomized programs that act more like circuits. Consider the class of programs, C, that contain randomized algorithms that work only a specific input length. For any C &#8712; C, we say C(x) is the random variable that simulates C on input x for time |C|, and outputs what C does if C terminates in time |C|, and outputs 0 otherwise. See that C behaves like circuits in the following important ways:</p><p>A few notes on using C in our proof, as opposed to circuits. </p><p>3. We also note that for some programs C &#8712; C, for some inputs x, our program C evaluated on x may answer one or zero with very close to half probability. That is, the syntax of C does not only give bounded error randomized algorithms, just a randomized algorithm. This is not an issue, because in the completeness case, there will be a program C that does have bounded error the prover should provide. And in the soundness case, the soundness of our PCP holds against any multi-prover strategy, even a randomized strategy. So no program provided will convince the verifier with high probability.</p><p>Finally, see that in all cases of our proof, Arthur only asks Merlin for a program computing some SPACE[O(n)] complete problem. This advice does not depend on the specific input, only on the input size.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Preliminaries</head><p>We assume some familiarity with basic complexity theory. See Arora and Barak's book for background <ref type="bibr">[1]</ref>. In this paper, by algorithm, we mean algorithm on a RAM machine, and by circuit, we mean a fan in 2 circuit with unbounded depth. A randomized algorithm is a deterministic algorithm with an extra input for randomness. We will assume in this paper that all time and space bounds for algorithms are sufficiently easily computable. Now recall that MA is the complexity class of problems with polynomial sized certificates that can be verified with bounded error by a randomized, polynomial time algorithm. This is like NP with a randomized verifier. Then we define MATIME in an analogous way to NTIME. Our results have perfect completeness, so we only define MATIME with perfect completeness.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>&#9654; Definition 10 (MATIME/1). For any function</head><p>as the set of languages, L, such that there is a function b : N &#8594; {0, 1} and a time f (n) randomized algorithm M taking four inputs, an input x, a random input r, a witness w, and an advice bit such that</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Soundness If x /</head><p>&#8712; L and n = |x|, then for every w,</p><p>We let SIZE denote the class of languages with circuits of a given size.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>&#9654; Definition 11 (SIZE). For any function</head><p>is the class of languages, L, where for each input length n, there is a circuit of size f (n) with n inputs computing L for inputs of length n.</p><p>In this paper, we will focus on time and space efficient, non-adaptive PCPs with perfect completeness. Because we need to pay close attention to the amount of time it takes to make a single query to the proof, we separate the algorithm for producing queries, Q, from the algorithm for verifying the response, V . We also separate the function that gives all the query locations for a choice of randomness, I, from the algorithm that gives a single one of those query locations, Q.</p><p>So at a high level, a PCP protocol does the following: 1. Chooses a common random string, r. 2. Runs query function Q with randomness r for q(n) many times to get all query locations, I.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>3.</head><p>Looks up all query locations, I, into a provided proof, &#960;, to get proof window &#960; I . 4. Runs verifier V with randomness r and proof window &#960; I and outputs if V accepts.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>55:9</head><p>Now we formally define a PCP.</p><p>&#9654; Definition 12 (PCP). We say that a language L has a non-adaptive PCP, A, with perfect completeness if there exists verifier V , prover P , index function I, and query function Q, such that, for some alphabet &#931;, &#948; &#8712; [0, 1], and functions r, l, q : N &#8594; N: 1. I takes 2 inputs, an input of length n and randomness of length r(n), and outputs an element of [l(n)] q(n) . That is, I outputs q(n) indexes in a length l(n) string, 2. Q is an algorithm with three inputs, an input x of length n, randomness r of length r(n), and an index i &#8712; [q(n)] and outputs an element of [l(n)] such that Q(x, r, i) = I(x, r) i .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>3.</head><p>V is an algorithm with three inputs, an input of length n, randomness of length r(n), and q(n) symbols from &#931;, and outputs either accept or reject.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.">P is an algorithm that takes two inputs, an input of length n, and an index</head><p>and outputs a symbol from &#931;.</p><p>Completeness If x &#8712; L and n = |x|, then there exists</p><p>and for every i</p><p>Then we also say:</p><p>1. A has proof length l(n).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>2.</head><p>A has alphabet &#931;.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>3.</head><p>A has soundness &#948;.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>4.</head><p>A uses q(n) queries.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>5.</head><p>A uses r(n) bits of randomness. </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Efficient PCP To Fine Grained Lower Bounds</head><p>We only give a detailed sketch here. The full version of our paper is available at <ref type="bibr">[9]</ref>. Our analysis depends on the circuit complexity of some PSPACE complete problem. So we start by choosing a SPACE[O(n)] complete problem. We use a version of SPACE TMSAT (on page 83 of <ref type="bibr">[1]</ref>).</p><p>&#9654; Definition 13 (Specific Problem). SPACE TMSAT is the language {(M, x, 1 n , 0 * ) : Turing machine M accepts x using at most n space.} Note: SPACE TMSAT &#8712; SPACE[O(n)] and SPACE TMSAT is SPACE[O(n)] complete. The 0 * is just there to make it explicit the language is paddable. In particular, this means that the circuit complexity of SPACE TMSAT is non-decreasing.</p><p>&#9654; Lemma 14 (SPACE TMSAT Circuit Complexity is Non-Decreasing). If A &#8242; (n) is the size of the minimum circuit solving SPACE TMSAT for inputs of length n, then A &#8242; (n) is non-decreasing.</p><p>Proof. Let C be the circuit of size A &#8242; (n + 1) solving SPACE TMSAT for length n + 1 inputs. Then to get a circuit for length n inputs, use C with an extra 0 hard coded into the last input. The resulting circuit will be at most the size of C and solve length n inputs. Thus A &#8242; (n + 1) &#8805; A &#8242; (n). &#9664;</p><p>Then using Theorem 3, we can get a PCP for SPACE TMSAT by setting T = 2 O(n) and S = O(n). This can be turned into a PCP with a binary alphabet by replacing every query for a symbol in &#931; with O(log(n)) queries to the individual bits of that symbol.</p><p>&#9654; Corollary 15 (PCP for SPACE TMSAT). There is a PCP for SPACE TMSAT with: 1. Verifier time &#213;(n).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Query time &#213;(n).</head><p>3. poly(log(n)) queries. 4. Binary alphabet. 5. Log of proof length &#213;(n). 6. Prover space &#213;(n). 7. Soundness 1/2 and perfect completeness.</p><p>We prove three different MATIME/1 lower bounds that are based on three different hard problems. Different ones work better in different parameter regimes. After constructing them all, we show we always fall into some range of parameters so that we can get the lower bounds of Theorem 1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">Implicitly Encoding Advice in Input Length</head><p>In each of our cases, we will use advice to find the size of some prover circuit. To do this, we implicitly encode a number in the input length. If that implicitly encoded number describes the size, our advice bit will be 1. Otherwise, the advice bit is 0.</p><p>For any input length n &#8712; N, for some l &#8712; N, we have n &#8712; [2 l , 2 l+1 ). For such an l, there is some m &#8712; N such that n = 2 l + m. This m, or equivalently this l, is our implicitly encoded number. Because we will use this decomposition a lot, we will explicitly define some functions that perform this decomposition.</p><p>&#9654; Definition 16 (Implicit Encoding In Input). For natural n &#8805; 1, let l &#8805; 0 be an integer so that n &#8712; [2 l , 2 l+1 ), and m &#8805; 0 be an integer so that n = 2 l + m. Then define &#181;(n) = m and &#961;(n) = l.</p><p>There is a simple interpretation of this m = &#181;(n) and l = &#961;(n) in terms of the binary representation of n. You can think of l as the length of the binary number, and m the binary number after the top bit is removed.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">SPACE TMSAT not in P/poly</head><p>In this case, we follow the proof in the original work <ref type="bibr">[29]</ref> where PSPACE &#824; &#8834; P/poly. We present the same arguments here with more precise parameters.</p><p>When PSPACE &#824; &#8834; P/poly, the circuit complexity of SPACE TMSAT for different input sizes could change drastically and in a way that may be hard to analyze. This is an issue because the PCP for SPACE TMSAT needs a prover with a longer input than the input being verified, thus might require a much larger circuit.</p><p>Instead, we use a downward self reducible PSPACE complete language. Specifically, a language that has a sound interactive protocol with queries the same length as its input and whose prover is the language itself. We cite the result from Lemma 11 in <ref type="bibr">[29]</ref>:</p><p>&#9654; Lemma 17 (Same Size, Self Proving PSPACE Complete Language). There is a PSPACEcomplete language Y and a probabilistic polynomial-time oracle Turing machine M such that for any input x: 1. M only asks its oracle queries of length |x|.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>2.</head><p>If M is given Y as oracle and x &#8712; Y , then M accepts with probability 1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">If x /</head><p>&#8712; Y , then irrespective of the oracle given to M , M rejects with probability at least 1/2.</p><p>The important feature of language Y is that for an input x, the prover for x is the same language Y , and queries to the prover have the same length as x. This means Y , and the prover for Y , have the same circuit. Then if PSPACE &#824; &#8834; P/poly, then the polynomial overhead of the proof protocol grows much more slowly than the difficulty of Y . So a padded version of Y can be used as our language in this case. A proof sketch is in Appendix A, full proofs are in the full version <ref type="bibr">[9]</ref>.</p><p>&#9654; Lemma 18 (Bound if PSPACE does not have Polynomial Sized Circuits). If SPACE TMSAT / &#8712; P/poly, then for any k &gt; 0, and some f (n) = o(1):</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3">SPACE TMSAT in Almost Linear Size</head><p>The idea in this case is to use a brute force, small space algorithm that finds a problem not in a fixed polynomial size. In particular, for circuit size S(n), the brute force algorithm uses space O(S(n)) to compute some function with minimum circuit size &#920;(S(n)). Then we want to simulate the PCP from Corollary 15 to prove the output of this algorithm. Since the PCP is efficient, the prover for this algorithm does not use much more space than the brute force algorithm itself.</p><p>If SPACE TMSAT has almost linear sized circuits, the prover doesn't require much larger circuits than the space of the prover. Finally, our PCP is efficient, so the time of the MA verifier isn't much more than the size of the prover circuit. So the MA protocol doesn't require much more time then the size of the circuit it proves the output of.</p><p>If SPACE TMSAT requires larger circuits, say quadratic circuits, then the size of the prover circuits would be quadratically larger than the input length of the prover. That is, the prover circuit would be quadratically larger than the circuit it is trying to prove. This would give quadratic overhead for the MA verifier time over the size of the circuit it verifies. So this construction only works well enough when SPACE TMSAT has almost linear sized circuits.</p><p>So this gives a proof when SPACE TMSAT has almost linear sized circuits. A proof sketch is in Appendix A, full proofs are in the full version <ref type="bibr">[9]</ref>. <ref type="formula">1</ref>) and some non-decreasing function</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.4">SPACE TMSAT in Polynomial Size, but not Almost Linear</head><p>This is the "bad" case, where we can't prove the result for every constant k, only for k &lt; a. This is the most complicated case, requiring us to both pad the input to get the correct problem difficulty, and use advice to get the size of the circuits for the prover. The idea is to solve SPACE TMSAT on a padded version of the input using our PCP. So we need the advice to tell us three things:</p><p>1. Some m so that SPACE TMSAT on length m inputs requires circuits of size &#969;(n k ). 2. Further, we need SPACE TMSAT on length m inputs to require circuits of size near m a . This keeps the prover from requiring circuits too much larger than SPACE TMSAT on length m inputs does. 3. How big the circuit for the prover in Corollary 15 needs to be.</p><p>Similar to the previous cases, this advice will come implicitly from the input length, and the single advice bit will be 1 if and only if the input length encodes valid advice. A skectch is in Appendix A. For full details, see the full version <ref type="bibr">[9]</ref>.</p><p>&#9654; Lemma 20 (Bound if SPACE TMSAT has size n a+o (1) ). Suppose for some function h <ref type="formula">1</ref>) and for some constant a &gt; 1, for function</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>non-decreasing and we have SPACE TMSAT &#8712; SIZE[O(A(n))] \ SIZE[o(A(n))],</head><p>then for any k &lt; a, for some</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.5">Altogether</head><p>Altogether, these three cases imply Theorem 1. More details can be found in the full version <ref type="bibr">[9]</ref>.</p><p>&#9654; Theorem 1 (Fine Grained MA Lower Bound). There exists a constant a &gt; 1, such that for all k &lt; a, for some</p><p>Proof. First, we will find the best polynomial approximation of the circuit complexity of SPACE TMSAT. Then the set S is nonempty and has a lower bound. So S has an infimum, a, so that for any constant &#1013; &gt; 0, we have </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">PCP Sketch</head><p>We give a brief overview of the PCP proof. A full proof is available at <ref type="bibr">[9]</ref>. Our overall protocol constructs an extrapolatable PCP by observing that a simple BFL style PCP is extrapolatable. Then this can be turned into an rPCP with an efficient query function. Finally we can compose this with a decodable, BFL style PCP with a very fast verifier.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1">Extrapolatable PCPs</head><p>We start by showing some lemmas about extrapolatability that make the definition easy to work with. Notably, if 2 functions are extrapolatable, so is their concatenation. This allows us to show components of a PCP are extrapolatable individually to get an extrapolatable PCP.</p><p>&#9654; Lemma 21 (Extrapolatability Combination). For integers n, q, q &#8242; , t, t &#8242; &gt; 0, and field F, if p : [q] &#8594; F n is t extrapolatable, and</p><p>Of course, extrapolatability's main purpose is to allow efficient extrapolation.</p><p>&#9654; Lemma 22 (Efficient Polynomials From Extrapolatability). For any n, q, t &gt; 0, field F where |F| &gt; q, and t extrapolatable Q :</p><p>algorithm computing the value of a degree q -1 polynomial, g, such that for all i &#8712; [q] we have</p><p>Now we introduce extrapolatable PCPs and show they imply robust PCPs with fast query functions. Extrapolatable PCPs are PCPs whose proofs are low degree functions, only require soundness against proofs that are low degree functions, and whose query location function is extrapolatable.</p><p>In our notation, the query function Q returns a single query location of the verifier V on a choice of randomness, whereas I returns every query location for a choice of randomness. Query function, Q, needs to be extrapolatable, but index function, I, is more convenient for defining completeness and soundness. See standard PCPs, Definition 12, for reference.</p><p>&#9654; Definition 23 (Extrapolatable PCP). We say a non-adaptive PCP, A, for language L with verifier V , prover P , individual query function Q, and index function I is an extrapolatable PCP (ePCP) if for some m and d: 1. For some field F, A uses alphabet F.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">The proof length is |F| m .</head><p>That is, any proof, &#960;, can be viewed as a function &#960; : F m &#8594; F.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Low Degree Completeness If</head><p>x &#8712; L and n = |x|, then there exists a polynomial &#960; x :</p><p>Further, we say A has:</p><p>extrapolatable.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Degree d and m variables.</head><p>3. Low degree soundness &#948;. 4. Perfect low degree completeness.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2">Constructing our Extrapolatable PCP</head><p>Our ePCP is a BFL <ref type="bibr">[4]</ref> style PCP. We start by converting our algorithm into a cellular automata so that it has very uniform, local constraints, similar to the Cook-Levin theorem <ref type="bibr">[10,</ref><ref type="bibr">21]</ref>, or what was done in <ref type="bibr">[20]</ref>. In particular, the constraints can be described by a simple polynomial of the computation history of the cellular automata.</p><p>Then our ePCP will ask for a multilinear extension of the computation history, a low degree polynomial encoding the constraint function of that computation history, and a sum check [22] style proof verifying that constraint is always satisfied. Then the verifier just needs to check the computation history is consistent with the input, the constraint polynomial is consistent with the computation history polynomial, and the sum check of the constraint polynomial succeeds. All low degree testing is handled in the conversion from an ePCP to an rPCP. Now we verify that a variation on standard sum check <ref type="bibr">[22,</ref><ref type="bibr">4]</ref> is extrapolatable. Since ePCPs only need soundness against low degree proofs, our base ePCP only needs to perform constantly many queries besides the sum check. So the check sum is the most difficult thing to prove the extrapolatability of.</p><p>&#9654; Lemma 25 (Sum Check Queries Are Extrapolatable). For any variable number n &#8712; N, degree d &#8712; N, field F with |F| &gt; max{d, n} + 1, and randomness r, the query location function, Q r , used in the sum check protocol for a degree d and n variable function are O(ndpolylog(|F|)) extrapolatable.</p><p>The proof is straightforward and comes from a close observation of the specific sum check query locations.</p><p>We need a low space prover to use in our MA lower bounds. Creating the computation history itself takes about as much space as the original algorithm. Multilinear extensions can be done straightforwardly in small space if one only needs one symbol, or does not care about time.</p><p>&#9654; Lemma 26 (Multilinear Extensions Require Low Space). Suppose function G : {0, 1} n &#8594; {0, 1} is computable in space S. Then the multilinear function g consistent with G on Boolean inputs is computable in space O(n log(|F|) + S).</p><p>Similarly, individual symbols from the constraint polynomial can be computed in small space from the multilinear extension of the computation history. The sum check proof is essentially partial linearizations of the constraint polynomial, so can also be done in small space.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.3">Decodable PCP</head><p>After that, we use a similar PCP for the decodable inner PCP (dPCP), and apply a standard robust, decodable PCP composition <ref type="bibr">[12]</ref>. Essentially only two changes need to be made to get our dPCP. First we need to only check consistency of the computation history with the explicit input (and not the implicit input). Second, we need to do an additional query to an implicit input to decode from it. This does not require any new tricks.</p><p>Finally, we do a standard PCP composition of a robust PCP with a decodable PCP to do query reduction. We note that we can not do the standard trick of having the outer rPCP output a circuit that the inner dPCP proves the output of as that circuit description would be too large for a verifier to compute. Instead this must be done implicitly, similar to <ref type="bibr">[5]</ref>. We also note that to keep the space of the inner PCP prover small requires the space of the outer PCP prover, the space of the outer query function, and the space of the outer PCP verifier to be small.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.4">Fine Grained MIP = NEXP</head><p>We note that the low space and deterministic algorithm requirements were only to keep the prover space low. Dropping the prover space requirement and using the same proof gives Theorem 4. Then using Theorem 4, one can use a standard technique to get</p><p>error, 2 query PCP. Combining this with a repetition theorem <ref type="bibr">[28,</ref><ref type="bibr">19,</ref><ref type="bibr">27]</ref> gives the 2 query, constant error MIP stated in Corollary 5.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Open Problems</head><p>There are several ways we would like to improve the circuit lower bounds.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>1.</head><p>Remove the advice bit. We still had to use advice, a limitation from the original Santhanam result. It would be nice if we could get lower bounds on MA with no non-uniformity.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Prove tight bounds for all k.</head><p>Another limitation of our circuit lower bound is that it does not prove this tight bound for all k &gt; 1, just for some k.</p><p>The major barrier is in the case that SPACE[n] algorithms may require super linear, but polynomial, sized circuits. Then the circuit size required for any given space may change in a strange way. For example, suppose for some a &gt; 1</p><p>What we would like, but this does not obviously imply, is that for all b &gt; 1: We only prove that infinitely often this lower bound occurs, but it may have even super exponential gaps between input sizes where the circuit lower bound holds. Murray and Williams <ref type="bibr">[26]</ref> gave a refinement of the Santhanam circuit lower bounds, that is incomparable to ours, which gives circuit lower bounds that holds for input lengths only polynomially far apart.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.">Prove exponential lower bounds for MAEXP.</head><p>A similar problem is to prove exponential circuit lower bounds for the exponential version of MA, known as MAEXP. The best circuit lower bounds known for MAEXP are "half-exponential" by Miltersen, Vinodchandran, and Watanabe <ref type="bibr">[24]</ref>. Loosely, a function is half exponential if that function composed with itself is exponential.</p><p>Another open problem is to give a PCP whose verifier time matches ours with only quasilinear proof length. Known PCPs with proof length &#213;(T ) have verifier time &#8486;(n + log(T ) 2 ). We suspect ideas from theorem 2.6 in <ref type="bibr">[5]</ref> <ref type="foot">foot_3</ref> (which extends the results of <ref type="bibr">[7]</ref> from NP to NEXP) may give a PCP with verifier time near &#213;(n + log(T )) while giving a proof of length T 1+o (1) . But it would not have proof length &#213;(T ) = T polylog(T ). We stress that close analysis of the verifier time for the PCP of <ref type="bibr">[5]</ref> has not been performed, and that PCP is much more complex than ours.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A MA Circuit Lower Bound Proofs</head><p>In this section, we sketch the proofs of the main lemmas of Section 3. Full proofs are available in the full version <ref type="bibr">[9]</ref>.</p><p>&#9654; Lemma 18 (Bound if PSPACE does not have Polynomial Sized Circuits). If SPACE TMSAT / &#8712; P/poly, then for any k &gt; 0, and some f (n) = o(1):</p><p>Proof. The idea is to take length m inputs to Y , pad them up to length n inputs so that Y on length m inputs requires, and has, circuits of size just slightly larger than n k . Then as long as n grows much faster than m, the overhead of the interactive protocol verifier will be small and we only need to focus on prover overhead, which is around n k since the circuit for Y is the prover for Y .</p><p>First, I claim that, since Y / &#8712; P/poly, for some g</p><p>]. If this was not true, then Y must have circuits of size n k for some k upper bounding the best choice of g(n). Now we define our language, W , in MATIME[n k+f (n) ]/1 but not in SIZE[O(n k )]. For any input size, n, using Definition 16, let m = &#181;(n) and l = &#961;(n). Let our advice bit be 1 if both: 1. Y on length m inputs has circuits with size n k log(n). This makes sure there is a fast prover for Y . 2. And Y on length m inputs does not have circuits of size m g (m) . This makes sure m grows much more slowly than n. Then x &#8712; W for some x with |x| = n if and only if the advice bit is 1 and for some y &#8712; Y with |y| = m we have x = y1 n-m .</p><p>Let a &gt; 0 be the constant so that the verifier (M in Lemma 17) for Y 's interactive protocol runs in time O(n a ). Define the MA protocol as follows. If the trusted advice bit is one, Merlin gives Arthur a length n k log(n) circuit. Then Arthur simulates the interactive protocol for Y on y using the circuit from Merlin as the prover. This protocol runs in time O(m a n k log(n)). By assumption we have m g(m) &lt; n k log(n), which one can show implies m &lt; n f &#8242; (n) for some</p><p>By choice of g(m), for infinitely many m, the second condition is satisfied and g(m) &gt; k+1. For such m, the smallest choice of n = 2 l + m where Y on length m inputs has circuits of size n k log(n) can not have circuits of size (n/2) k log(n/2). For such n, language W does not have circuits of size O(n k ), but does have an MA protocol running in time n k+f (n) . &#9664; &#9654; Lemma 19 (Bound if SPACE TMSAT has Size n 1+o (1) ). If for some g(n) = o( <ref type="formula">1</ref>) and some non-decreasing function</p><p>Proof. The proof proceeds in five steps.</p><p>In particular, for every input length n, language L has circuits of size n k log(n) but not n k log(n)/10. 2. Reduce L to SPACE TMSAT and use Corollary 15. In particular, find a circuit, C n , for the prover in an MA protocol for L on length n inputs. 3. Define our advice bit to implicitly give an upper bound for the size of C m for some m within a factor of 2 of n. Then we define W to be length m elements of L, padded to length n. 4. Show that infinitely often the advice bit is 1 and W does not have small circuits. 5. Show that W has an efficient MA protocol.</p><p>With that outline in mind, let us begin the proof. From the non-uniform hierarchy (in Arora and Barak [1, Theorem 6.22]), there is a language L &#8712; SIZE[n k log(n)] \ SIZE[n k log(n)/10]. In particular, for every n, language L on length n has circuits size n k log(n) but not size n k log(n)/10. A brute force search can then find and simulate such a circuit using space O(n k log(n) 2 ). Since M only uses space g(n) = &#213;(n k ), we know x &#8712; L if and only if (M, x, 1 g(n) , 0) &#8712; SPACE TMSAT. We know SPACE TMSAT on length &#213;(n k ) inputs has a PCP protocol from Corollary 15 that uses polylog(n) many length &#213;(n k ) queries to a space &#213;(n k ) prover, P , where each query can be calculated by a time &#213;(n k ) algorithm, Q, and the results from P are verified by a time &#213;(n k ) verifier, V . Now we reduce the prover P to SPACE TMSAT so we can use that SPACE TMSAT &#8712; SIZE[O(n 1+g(n) )] to get a circuit for P . A length &#213;(n k ) query, q, to P can be converted into a length &#213;(n k ) input, q &#8242; , for SPACE TMSAT by providing the algorithm for P and &#213;(n k ) 1s. Call the circuit for SPACE TMSAT on length |q &#8242; | inputs C n . Since SPACE TMSAT &#8712; SIZE[O(n 1+g(n) )], we know C n has size ( &#213;(n k )) 1+g(n) = n k+g &#8242; (n) for some g &#8242; (n) = o(1). 3. Define our advice bit. Now an MA protocol can guess C n , but we may not be able to compute how large C n needs to be. The function g &#8242; (n) may be hard to compute. So we use advice.</p><p>Let l = &#961;(n), m = 2 l and t = &#181;(n) so that n = m + t. Then let the advice bit be 1 if a. Circuit C m has size m k 2 t . b. For any natural t &#8242; less than t, circuit C m does not have size m k 2 t &#8242; . This condition allows us to use the smallest t possible for a given m. Then x &#8712; W for some x with |x| = n if and only if the advice bit is 1 and for some y &#8712; SPACE TMSAT with |y| = m we have x = y1 n-m . 4. Show W does not have small circuits.</p><p>First see that for every large enough l, for m = 2 l , there will be one t such that this advice bit is 1. That is for some t &lt; m, C m has size m k 2 t . Otherwise, C m would have exponential size, but it only has almost linear size. Then for the minimum such t, the advice bit will be one. So infinitely often, the advice bit will be 1.</p><p>When the advice bit is 1, the language W on length n = m + t inputs is equal to L on length m inputs.  </p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>The PCP constructed by Holmgren and Rothblum was built to have no signalling soundness and has many steps that take longer than &#213;(log(T )) time to compute. Still, the basic elements of of their PCP needed for a standard PCP are computable in &#213;(n + log(T )) time.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_1"><p>This is a trichotomy in an asymptotic sense: for every constant a, either X &#8712; SIZE[O(n a )] or it is not. See Section</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" xml:id="foot_2"><p>3.5 for details.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="3" xml:id="foot_3"><p>We emphasize this is the theorem labeled "Efficient PCPPs with small query complexity", which does not have quasi-linear proof length.</p></note>
		</body>
		</text>
</TEI>
