View in EDS

Shorter arithmetization of nondeterministic computations.

Saved in:
Bibliographic Details
Title: Shorter arithmetization of nondeterministic computations.
Authors: Chiesa, Alessandro1 alexch@csail.mit.edu, Zhu, Zeyuan Allen1 zeyuan@csail.mit.edu
Source: Theoretical Computer Science. Oct2015, Vol. 600, p107-131. 25p.
Subjects: Computational complexity, Mathematical proofs, Encoding, QUERY (Information retrieval system), Logarithms, Machine theory
Abstract: Arithmetizing computation is a crucial component of many fundamental results in complexity theory, including results that gave insight into the power of interactive proofs, multi-prover interactive proofs, and probabilistically-checkable proofs. Informally, an arithmetization is a way to encode a machine's computation so that its correctness can be easily verified via few probabilistic algebraic checks. We study the problem of arithmetizing nondeterministic computations for the purpose of constructing short probabilistically-checkable proofs (PCPs) with polylogarithmic query complexity. In such a setting, a PCP's proof length depends (at least!) linearly on the length, in bits, of the encoded computation. Thus, minimizing the number of bits in the encoding is crucial for minimizing PCP proof length. In this paper we show how to arithmetize any T -step computation on a nondeterministic Turing machine by using a polynomial encoding of length O ( T ⋅ ( log ⁡ T ) 2 ) . Previously, the best known length was Ω ( T ⋅ ( log ⁡ T ) 4 ) . For nondeterministic random-access machines, our length is O ( T ⋅ ( log ⁡ T ) 2 + o ( 1 ) ) , while prior work only achieved Ω ( T ⋅ ( log ⁡ T ) 5 ) . The polynomial encoding that we use is the Reed–Solomon code. When combined with the best PCPs of proximity for this code, our result yields quasilinear-size PCPs with polylogarithmic query complexity that are shorter, by at least two logarithmic factors, than in all prior work. Our arithmetization also enjoys additional properties. First, it is succinct , i.e., the encoding of the computation can be probabilistically checked in ( log ⁡ T ) O ( 1 ) time; this property is necessary for constructing short PCPs with a polylogarithmic-time verifier. Furthermore, our techniques extend, in a certain well-defined sense, to the arithmetization of yet other NEXP-complete languages. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Arithmetizing computation is a crucial component of many fundamental results in complexity theory, including results that gave insight into the power of interactive proofs, multi-prover interactive proofs, and probabilistically-checkable proofs. Informally, an arithmetization is a way to encode a machine's computation so that its correctness can be easily verified via few probabilistic algebraic checks. We study the problem of arithmetizing nondeterministic computations for the purpose of constructing short probabilistically-checkable proofs (PCPs) with polylogarithmic query complexity. In such a setting, a PCP's proof length depends (at least!) linearly on the length, in bits, of the encoded computation. Thus, minimizing the number of bits in the encoding is crucial for minimizing PCP proof length. In this paper we show how to arithmetize any T -step computation on a nondeterministic Turing machine by using a polynomial encoding of length O ( T ⋅ ( log ⁡ T ) 2 ) . Previously, the best known length was Ω ( T ⋅ ( log ⁡ T ) 4 ) . For nondeterministic random-access machines, our length is O ( T ⋅ ( log ⁡ T ) 2 + o ( 1 ) ) , while prior work only achieved Ω ( T ⋅ ( log ⁡ T ) 5 ) . The polynomial encoding that we use is the Reed–Solomon code. When combined with the best PCPs of proximity for this code, our result yields quasilinear-size PCPs with polylogarithmic query complexity that are shorter, by at least two logarithmic factors, than in all prior work. Our arithmetization also enjoys additional properties. First, it is succinct , i.e., the encoding of the computation can be probabilistically checked in ( log ⁡ T ) O ( 1 ) time; this property is necessary for constructing short PCPs with a polylogarithmic-time verifier. Furthermore, our techniques extend, in a certain well-defined sense, to the arithmetization of yet other NEXP-complete languages. [ABSTRACT FROM AUTHOR]
ISSN:03043975
DOI:10.1016/j.tcs.2015.07.030