A PCP characterization of NP with optimal amortized query complexity
From MaRDI portal
Publication:3191985
DOI10.1145/335305.335329zbMath1296.68060OpenAlexW2091921997MaRDI QIDQ3191985
Luca Trevisan, Alex Samorodnitsky
Publication date: 26 September 2014
Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/335305.335329
Related Items (28)
Towards optimal lower bounds for clique and chromatic number. ⋮ On the approximability of clique and related maximization problems ⋮ Inapproximability results for equations over finite groups ⋮ Fast Heuristics and Approximation Algorithms ⋮ A note on unique games ⋮ A self-tester for linear functions over the integers with an elementary proof of correctness ⋮ Succinct NP Proofs from an Extractability Assumption ⋮ On the derandomization of the graph test for homomorphism over groups ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Finding large 3-free sets. I. The small \(n\) case ⋮ Breaking the ε-Soundness Bound of the Linearity Test over GF(2) ⋮ Approximability of Packing Disjoint Cycles ⋮ Approximation Algorithms for CSPs ⋮ Contact Center Scheduling with Strict Resource Requirements ⋮ Approximability of packing disjoint cycles ⋮ Unnamed Item ⋮ Inapproximability results for equations over infinite groups ⋮ Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ Linear-consistency testing. ⋮ New tools and connections for exponential-time approximation ⋮ Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ On non-optimally expanding sets in Grassmann graphs ⋮ Black-Box Reductions in Mechanism Design ⋮ On the hardness of approximating max-satisfy ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Unnamed Item ⋮ An Improved Dictatorship Test with Perfect Completeness
This page was built for publication: A PCP characterization of NP with optimal amortized query complexity
