Efficient checking of polynomials and proofs and the hardness of approximation problems
From MaRDI portal
Publication:1906841
DOI10.1007/3-540-60615-7zbMath0861.68042WikidataQ56017262 ScholiaQ56017262MaRDI QIDQ1906841
Publication date: 24 January 1996
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60615-7
68Q25: Analysis of algorithms and problem complexity
68-02: Research exposition (monographs, survey articles) pertaining to computer science
03F20: Complexity of proofs
Related Items
A Hierarchy Theorem for Interactive Proofs of Proximity, Constant-Round Interactive Proofs for Delegating Computation, Unnamed Item, A novel elementary construction of matching vectors, On quasilinear-time complexity theory, Non-interactive proofs of proximity, Algebraic testing and weight distributions of codes., Self-correcting polynomial programs, Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!, Limits on the Rate of Locally Testable Affine-Invariant Codes, Public Key Locally Decodable Codes with Short Keys, Short Locally Testable Codes and Proofs