A PCP characterization of NP with optimal amortized query complexity
From MaRDI portal
(Redirected from Publication:3191985)
Recommendations
Cited in
(44)- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- 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
- Smooth and strong PCPs
- 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
- PCP characterizations of NP: towards a polynomially-small error-probability
- Query efficient PCPs with perfect completeness
- Contact center scheduling with strict resource requirements
- A PCP characterization of AM
- Black-box reductions in mechanism design
- A self-tester for linear functions over the integers with an elementary proof of correctness
- Succinct NP Proofs from an Extractability Assumption
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- Two-query PCP with subconstant error
- Simple PCPs with poly-log rate and query complexity
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- scientific article; zbMATH DE number 1775415 (Why is no real title available?)
- Simple analysis of graph tests for linearity and PCP
- Query-efficient dictatorship testing with perfect completeness
- Approximation Algorithms for CSPs
- The quest for strong inapproximability results with perfect completeness
- Fast heuristics and approximation algorithms
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- An improved dictatorship test with perfect completeness
- Approximability of packing disjoint cycles
- Approximability of Packing Disjoint Cycles
- Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
- STACS 2005
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
- The PCP theorem by gap amplification
- The PCP theorem by gap amplification
- Linear-consistency testing.
- A novel GPU-based implementation of the cube attack
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Property testing with online adversaries
- Property testing with online adversaries
- A note on unique games
- Finding large 3-free sets. I. The small \(n\) case
- Inapproximability results for equations over infinite groups
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)
