An algebraic proof of the real number PCP theorem
DOI10.1016/J.JCO.2016.11.006zbMATH Open1370.68105OpenAlexW2559566311MaRDI QIDQ2396715FDOQ2396715
Authors: Martijn Baartse, Klaus Meer 
Publication date: 24 May 2017
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2016.11.006
Recommendations
probabilistically checkable proofsreal number model of computationalgebraic proofsPCP theorem for NP over the realstesting trigonometric polynomials
Computation over the reals, computable analysis (03D78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Computational Complexity
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Some optimal inapproximability results
- Title not available (Why is that?)
- The PCP theorem by gap amplification
- The PCP theorem for NP over the reals
- An Algebraic Proof of the Real Number PCP Theorem
- Almost transparent short proofs for \(\mathrm{NP}_{\mathbb R}\)
- Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)
- Testing Low Degree Trigonometric Polynomials
- Topics in real and complex number complexity theory
Cited In (6)
- Interactive proofs and a Shamir-like result for real number computations
- A PCP of proximity for real algebraic polynomials
- A Survey on Analog Models of Computation
- The PCP theorem for NP over the reals
- An Algebraic Proof of the Real Number PCP Theorem
- Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)
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 Q2396715)
