A PCP characterization of NP with optimal amortized query complexity

DOI10.1145/335305.335329zbMath1296.68060MaRDI 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

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Query-Efficient Dictatorship Testing with Perfect Completeness, The Quest for Strong Inapproximability Results with Perfect Completeness, Fast Heuristics and Approximation Algorithms, Approximation Algorithms for CSPs, An Improved Dictatorship Test with Perfect Completeness, Approximability of Packing Disjoint Cycles, Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions, Unnamed Item, Linear-consistency testing., A self-tester for linear functions over the integers with an elementary proof of correctness, Approximability of packing disjoint cycles, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, A note on unique games, Finding large 3-free sets. I. The small \(n\) case, Inapproximability results for equations over infinite groups, On the hardness of approximating max-satisfy, 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, On non-optimally expanding sets in Grassmann graphs, New tools and connections for exponential-time approximation, On the derandomization of the graph test for homomorphism over groups, Contact Center Scheduling with Strict Resource Requirements, Black-Box Reductions in Mechanism Design, Succinct NP Proofs from an Extractability Assumption, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP