Shorter arithmetization of nondeterministic computations.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 109357111 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Shorter arithmetization of nondeterministic computations. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Chiesa%2C+Alessandro%22">Chiesa, Alessandro</searchLink><relatesTo>1</relatesTo><i> alexch@csail.mit.edu</i><br /><searchLink fieldCode="AR" term="%22Zhu%2C+Zeyuan+Allen%22">Zhu, Zeyuan Allen</searchLink><relatesTo>1</relatesTo><i> zeyuan@csail.mit.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Oct2015, Vol. 600, p107-131. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+proofs%22">Mathematical proofs</searchLink><br /><searchLink fieldCode="DE" term="%22Encoding%22">Encoding</searchLink><br /><searchLink fieldCode="DE" term="%22QUERY+%28Information+retrieval+system%29%22">QUERY (Information retrieval system)</searchLink><br /><searchLink fieldCode="DE" term="%22Logarithms%22">Logarithms</searchLink><br /><searchLink fieldCode="DE" term="%22Machine+theory%22">Machine theory</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=109357111 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.tcs.2015.07.030 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 107 Subjects: – SubjectFull: Computational complexity Type: general – SubjectFull: Mathematical proofs Type: general – SubjectFull: Encoding Type: general – SubjectFull: QUERY (Information retrieval system) Type: general – SubjectFull: Logarithms Type: general – SubjectFull: Machine theory Type: general Titles: – TitleFull: Shorter arithmetization of nondeterministic computations. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Chiesa, Alessandro – PersonEntity: Name: NameFull: Zhu, Zeyuan Allen IsPartOfRelationships: – BibEntity: Dates: – D: 04 M: 10 Text: Oct2015 Type: published Y: 2015 Identifiers: – Type: issn-print Value: 03043975 Numbering: – Type: volume Value: 600 Titles: – TitleFull: Theoretical Computer Science Type: main |
| ResultId | 1 |
