Sub-constant error probabilistically checkable proof of almost-linear size
From MaRDI portal
Publication:626681
DOI10.1007/s00037-009-0278-0zbMath1213.68317MaRDI QIDQ626681
Publication date: 18 February 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-009-0278-0
68Q60: Specification and verification (program logics, model checking, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Composition of Low-Error 2-Query PCPs Using Decodable PCPs, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Mathematics of computation through the lens of linear equations and lattices, Tight bounds on subexponential time approximation of set cover and related problems, Three-Player Entangled XOR Games are NP-Hard to Approximate