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

DOI10.1145/1007352.1007362MaRDI QIDQ3580955zbMATHOpenAlexFDO

Authors Jonas Holmerin, Subhash 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)

Recommendations

• Combinatorial PCPs with efficient verifiers
• Efficient formal verification of bounds of linear programs
• scientific article; zbMATH DE number 1285794
• A formally verified solver for homogeneous linear Diophantine equations
• NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations
• Problem-oriented verification system and its application to linear algebra programs
• NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine congruences and equations
• NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine discongruences
• Parallel Processing and Applied Mathematics
• A PCP theorem for interactive proofs and applications

Cited in

(6)

• Complexity and approximation of finding the longest vector sum
• On the hardness of learning intersections of two halfspaces
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Complexity of approximating CSP with balance/hard constraints
• Improved approximation algorithms for projection games
• On the hardness of approximating balanced homogenous 3-Lin

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580955)