Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
type: Item
instance of: scholarly article
title: Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
author: Oded Goldreich
author: Tom Gur
published in: Theoretical Computer Science
publication date: 2021-07-22T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7373868
zbMATH Keywords: property testing
zbMATH Keywords: coding theory
zbMATH Keywords: locally testable codes
zbMATH Keywords: probabilistic proof systems
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.05.030
OpenAlex ID: W3168770271
Wikidata QID: Q113863196
cites work: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
cites work: Some 3CNF properties are hard to test
cites work: Simple PCPs with poly-log rate and query complexity
cites work: Distribution Testing Lower Bounds via Reductions from Communication Complexity
cites work: Proofs of Proximity for Distribution Testing
cites work: Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
cites work: The PCP theorem by gap amplification
cites work: Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
cites work: Fast approximate probabilistically checkable proofs
cites work: Interactive proofs and the hardness of approximating cliques
cites work: Computational Complexity
cites work: Q4578332
cites work: Q4601820
cites work: Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
cites work: Locally testable codes and PCPs of almost-linear length
cites work: An Exponential Separation Between MA and AM Proofs of Proximity
cites work: Q5857610
cites work: Non-Interactive Proofs of Proximity
cites work: A Hierarchy Theorem for Interactive Proofs of Proximity
cites work: The Probabilistic Communication Complexity of Set Intersection
cites work: Algebraic methods for interactive proof systems
cites work: Property Testing of Massively Parametrized Problems – A Survey
cites work: Constant-round interactive proofs for delegating computation
cites work: Interactive proofs of proximity
cites work: Robust Characterizations of Polynomials with Applications to Program Testing
cites work: Time-Optimal Interactive Proofs for Circuit Evaluation
DOI: 10.1016/J.TCS.2021.05.030
description: scientific article; zbMATH DE number 7373868