A new PCP outer verifier with applications to homogeneous linear equations and max-bisection

DOI10.1145/1007352.1007362zbMath1192.68324OpenAlexW2010886177MaRDI QIDQ3580955

Jonas Holmerin, Subhash A. Khot

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007362

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Complexity of approximating CSP with balance/hard constraints ⋮ On the hardness of learning intersections of two halfspaces ⋮ Improved approximation algorithms for projection games ⋮ Complexity and approximation of finding the longest vector sum ⋮ Unnamed Item

This page was built for publication: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection