
Research
Abstracts  2007 
Verifying and Decoding in Constant DepthDan Gutfreund, Alexander Healy, Tali Kaufman & Guy N. RothblumSummaryWe introduce a general approach for improving the efficiency of a computationally bounded receiver interacting with a powerful and possibly malicious sender. The key idea we use is that of delegating some of the receiver's computation to the (potentially malicious) sender. We use tools from cryptography that allow us to do this safely, even when the sender is malicious. A classic example of such a senderreceiver setting is interactive proof systems. By taking the sender to be a (potentially malicious) prover and the receiver to be a verifier, we show that (pprover) interactive proofs with k rounds of interaction are equivalent to (pprover) interactive proofs with k+O(1) rounds, where the verifier is in NC0. That is, each round of the verifier's computation can be implemented in constant parallel time. As a corollary, we obtain interactive proof systems, with (optimally) constant soundness, for languages in AM and NEXP, where the verifier runs in constant paralleltime. Another, less immediate, senderreceiver setting arises when considering error correcting codes. By taking the sender to be a (potentially corrupted) codeword and the receiver to be a decoder, we obtain explicit families of codes that are locally (list)decodable by constantdepth circuits of size polylogarithmic in the length of the codeword. Using the tight connection between locally listdecodable codes and averagecase complexity, we obtain a new, more efficient, worstcase to averagecase reduction for languages in EXP. BackgroundIn this work we consider settings in which a computationally powerful but possibly malicious sender interacts with a weak and honest receiver. We explore the approach of improving the receiver's efficiency by delegating most of its computational work to the sender. It is not immediately apparent how to do this, as the sender may be malicious, and thus we introduce tools for reliably delegating computation to a potentially malicious party. We apply our approach to the settings of proof verification and error correcting codes. Proof Verification. Proof verification is a central concept in theoretical computer science. In this setting, a computationally powerful and possibly malicious party, the prover, interacts with a weak and honest party, the verifier. The prover makes a claim (e.g., that a given graph is 3colorable), and tries to convince the verifier that this claim is valid. The goal is to design a (possibly randomized and/or interactive) proof system such that the verifier is only convinced when the prover's claim is in fact correct, even when the prover behaves maliciously. Proof verification is perhaps the most natural example in complexity theory of a weak receiver interacting with a potentially malicious powerful sender. Here, the prover plays the part of the sender and the verifier plays the role of the weak receiver. Seminal works in complexity theory have uncovered the striking power of interactive and randomized proof systems as introduced by Babai [1] and Goldwasser, Micali and Rackoff [5]. The works of Shamir [8], and Babai, Fortnow and Lund [2], give efficient proof systems for every language that could conceivably have them. The works of Babai and Moran [3], Goldwasser and Sipser [6], Feige and Lovasz [4], and the PCP literature, show that interactive proof systems remain very powerful even when various limitations are placed on the verifier or on the protocol. In this work we continue this line of research, exploring the power of proof systems with verifiers that have very limited computational resources. We show that proof systems remain powerful even when the verifier is severely weakened computationally to run in NC0 (constant parallel time). ErrorCorrecting Codes. Error correcting codes are highly useful combinatorial objects. In this setting, a given message is encoded with some redundancy to obtain a codeword (longer than the original message) with the property that the original message can be recovered from any word that is close (in Hamming distance) to the codeword. The process of recovering the message from a (possibly) corrupted codeword is called decoding. Several variations on the standard notion of decoding have been considered in the literature. In some cases the codeword is corrupted in so many locations that recovering the original message becomes impossible. However, it might still be possible to recover a (short) list of candidate messages that is guaranteed to contain the original message  this is known as list decoding. One can also consider the task of recovering only a single bit of the message (in some given location) by accessing only a small number of locations in the codeword. Codes with such local decoding properties are called locally decodable codes and locally listdecodable codes. See the survey of Trevisan [10] for a more detailed discussion of these notions. In this work we focus on the efficiency of the decoder in locally decodable and locally listdecodable codes. We show explicit families of codes that are locally and locally list decodable by constant depth decoders (circuits) of size polylogarthmic in the length of the codeword. Our ResultsProof Verification. We consider proof systems with extremely weak verifiers: i.e., verifiers in NC0 (or constant parallel time). By that we mean that the verifier's strategy at each interaction round can be computed in NC0 when given access to the input, the randomness, and the messages exchanged in the previous rounds. We show that such proof systems are surprisingly powerful: essentially, anything that is provable in $k$ communication rounds with a polynomialtime verifier is also provable in k + O(1) communication rounds with an NC0 verifier. In particular, we obtain the following characterizations: 1. A language is in AM (the class of languages that have a proof system with a constant number of communication rounds) if and only if it has a singleprover, tworound, constantsoundness interactive proof that can be verified in constant parallel time. In particular, every language in NP has such a proof system. 2. A language is in NEXP if and only if it has a twoprover, fiveround, constantsoundness interactive proof that can be verified in constant parallel time. We complement our positive results with two negative results. First, we show that constantround proof systems with an NC0 verifier cannot have subconstant soundness (unless the language itself is in NC0). Second, we show that there is no publiccoin proof system with an NC0 verifier (again, unless the language itself is in NC0). This result sheds light on private vs. public coins proof systems and in particular on our protocols (which, naturally, use private coins). In particular, it shows that both interaction and private randomness are provably essential for nontrivial NC0 verification. ErrorCorrecting Codes. The application of our methodology to the setting of errorcorrecting codes is a novel approach to the wellstudied problem of efficient decoding. The sender embeds information in the codeword that helps speedup the decoder's computation. In our new codes, the decoder uses the received word not only for reconstructing information about the original message, but also as a computational resource. This approach allows us to transform locally (list)decodable codes with NC1 decoders into codes that have AC0 decoders (with similar or slightly worse parameters). We then construct explicit locallydecodable and locally listdecodable codes with NC1 decoders, and by applying our general transformations to these explicit codes, we obtain the following results: 1. An explicit binary code with polynomial rate and (probabilistic) AC0 localdecoding from a word that is corrupted in a constant fraction of locations. This code has roughly the same parameters as the canonical example of a locallydecodable binary code with polynomial rate (see [9]). 2. An explicit family of (nonbinary) codes that are locally listdecodable from agreement ? with list size poly(1/?) by probabilistic AC0 circuits of size poly(log M/?), where M is the length of the message. The alphabet size and codeword length of these codes match the recent construction of Impagliazzo, Jaiswalss [7]. (Indeed, our construction is based on the approximate codes of [7].) SupportThis research was supported by NSF grant CNS0430450 and NSF grant CFF0635297. References:[1] L. Babai. Trading Group Theory for Randomness. STOC 1985: 421429. [2] L. Babai, L. Fortnow and C. Lund. NonDeterministic Exponential Time has TwoProver Interactive Protocols. FOCS 1990: 1625. [3] L. Babai and S. Moran, ArthurMerlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes, Journal of Computer and System Sciences 36:254276, 1988. [4] U. Feige and L. Lovasz, Twoprover oneround proof systems, their power and their problems. STOC 1992: 733744. [5] S. Goldwasser, S. Micali and C. Rackoff. The Knowledge Complexity of Interactive ProofSystems. SIAM Journal on Computing 18(1):186208, 1989. [6] S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems. Advances in Computing Research 5:7390, 1989. [7] Russell Impagliazzo, Ragesh Jaiswal and Valentine Kabanets, Approximately ListDecoding Direct Product Codes and Uniform Hardness Amplification. FOCS 2006: 187196. [8] A. Shamir, IP = PSPACE. FOCS 1990: 1115. [9] M. Sudan, L. Trevisan and S. Vadhan, Pseudorandom generators without the XOR Lemma, STOC 1990: 537546, [10] L. Trevisan, Some Applications of Coding Theory in Computational Complexity. Quaderni di Matematica 13: 347424, 2004. 

