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
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
