A PCP characterization of NP with optimal amortized query complexity
From MaRDI portal
Publication:3191985
DOI10.1145/335305.335329zbMATH Open1296.68060OpenAlexW2091921997MaRDI QIDQ3191985FDOQ3191985
Authors: Alex Samorodnitsky, Luca Trevisan 
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
Recommendations
Cited In (38)
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Fast Heuristics and Approximation Algorithms
- Approximability of Packing Disjoint Cycles
- Query efficient PCPs with perfect completeness
- On the hardness of approximating max-satisfy
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- Inapproximability results for equations over infinite groups
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- A note on unique games
- Approximability of packing disjoint cycles
- Black-box reductions in mechanism design
- A Novel GPU-Based Implementation of the Cube Attack
- Query-efficient dictatorship testing with perfect completeness
- Finding large 3-free sets. I. The small \(n\) case
- Linear-consistency testing.
- Simple analysis of graph tests for linearity and PCP
- STACS 2005
- The Quest for Strong Inapproximability Results with Perfect Completeness
- On the approximability of clique and related maximization problems
- An Improved Dictatorship Test with Perfect Completeness
- Two-query PCP with subconstant error
- Title not available (Why is that?)
- A self-tester for linear functions over the integers with an elementary proof of correctness
- Title not available (Why is that?)
- On the derandomization of the graph test for homomorphism over groups
- Approximation Algorithms for CSPs
- A PCP characterization of AM
- Title not available (Why is that?)
- The PCP theorem by gap amplification
- Simple PCPs with poly-log rate and query complexity
- On non-optimally expanding sets in Grassmann graphs
- Towards optimal lower bounds for clique and chromatic number.
- Succinct NP Proofs from an Extractability Assumption
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- New tools and connections for exponential-time approximation
- Inapproximability results for equations over finite groups
- Contact center scheduling with strict resource requirements
- Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
This page was built for publication: A PCP characterization of NP with optimal amortized query complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191985)
