A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
DOI10.1145/1007352.1007362zbMATH Open1192.68324OpenAlexW2010886177MaRDI QIDQ3580955FDOQ3580955
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
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (6)
- On the hardness of approximating balanced homogenous 3-Lin
- Complexity and approximation of finding the longest vector sum
- Complexity of approximating CSP with balance/hard constraints
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Improved approximation algorithms for projection games
- On the hardness of learning intersections of two halfspaces
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)
