Efficient probabilistic checkable proofs and applications to approximation
From MaRDI portal
Publication:2817678
DOI10.1145/195058.195467zbMath1345.68144OpenAlexW4246874244MaRDI QIDQ2817678
Alexander Russell, Shafi Goldwasser, Mihir Bellare, Carstent Lund
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195467
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Approximation algorithm for stochastic set cover problem, Class Steiner trees and VLSI-design, Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
