An Algebraic Proof of the Real Number PCP Theorem

DOI10.1007/978-3-662-48054-0_5MaRDI QIDQ2946376zbMATH OpenOpenAlexFDO

Authors Martijn Baartse, Klaus Meer

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48054-0_5

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• An algebraic proof of the real number PCP theorem
• scientific article; zbMATH DE number 1336414
• A PCP of proximity for real algebraic polynomials
• The PCP theorem for NP over the reals
• The PCP theorem for NP over the reals
• An Algebraic Proof of Deuber's Theorem
• scientific article; zbMATH DE number 775663
• On Dinur’s proof of the PCP theorem
• An algebraic proof of van der Waerden's theorem
• scientific article; zbMATH DE number 4204456

Cites work

• Algebraic methods for interactive proof systems
• Almost transparent short proofs for \(\mathrm{NP}_{\mathbb R}\)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Testing Low Degree Trigonometric Polynomials
• The PCP theorem by gap amplification
• The PCP theorem for NP over the reals
• Topics in real and complex number complexity theory
• Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)

Cited in

(3)

• A PCP of proximity for real algebraic polynomials
• An algebraic proof of the real number PCP theorem
• The PCP theorem for NP over the reals

This page was built for publication: An Algebraic Proof of the Real Number PCP Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946376)