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