Sub-constant error probabilistically checkable proof of almost-linear size

DOI10.1007/s00037-009-0278-0zbMath1213.68317OpenAlexW2018791461MaRDI QIDQ626681

Ran Raz, Dana Moshkovitz

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

zbMATH Keywords

probabilistically checkable proof (PCP)almost-linear sizebalanced curvessub-constant error

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Mathematics of computation through the lens of linear equations and lattices ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ Tight bounds on subexponential time approximation of set cover and related problems

This page was built for publication: Sub-constant error probabilistically checkable proof of almost-linear size