PCP characterizations of NP: toward a polynomially-small error-probability
type: Item
instance of: scholarly article
title: PCP characterizations of NP: toward a polynomially-small error-probability
zbMATH Open document ID: 1234.68133
author: Irit Dinur
author: Eldar Fischer
author: Guy Kindler
author: Ran Raz
author: Shmuel Safra
published in: Computational Complexity
publication date: 2011-11-30T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5982632
zbMATH Keywords: NP
zbMATH Keywords: PCP
zbMATH Keywords: sum-check
zbMATH Keywords: consistent-reader
zbMATH Keywords: low-degree extension
zbMATH Keywords: representation-procedure
MaRDI profile type: Publication
full work available at URL: s00037-011-0014-4
OpenAlex ID: W1992067909
cites work: Q4218098
cites work: Proof verification and the hardness of approximation problems
cites work: Probabilistic checking of proofs
cites work: Q4527016
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: A well-characterized approximation problem
cites work: On the hardness of approximating minimization problems
cites work: Q4527015
cites work: A Parallel Repetition Theorem
DOI: 10.1007/S00037-011-0014-4
description: scientific article; zbMATH DE number 5982632