Query efficient PCPs with perfect completeness

DOI10.4086/TOC.2005.V001A007MaRDI QIDQ3002760zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Johan Hastad

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2005.v001a007

zbMATH Keywords

amortized query bitsapproximation algorithmscomputational complexityinapproximabilityPCPperfect completenessprobablistically checkable proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• STACS 2005
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Three‐query PCPs with perfect completeness over non‐Boolean domains
• A PCP characterization of NP with optimal amortized query complexity
• Towards an optimal query efficient PCP?

Cited in

(21)

• On non-optimally expanding sets in Grassmann graphs
• Succinct non-interactive arguments via linear interactive proofs
• New tools and connections for exponential-time approximation
• Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
• Strong inapproximability of the shortest reset word
• Stronger methods of making quantum interactive proofs perfectly complete
• Towards an optimal query efficient PCP?
• A query efficient non-adaptive long code test with perfect completeness
• Simple PCPs with poly-log rate and query complexity
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• scientific article; zbMATH DE number 1522925 (Why is no real title available?)
• Combinatorial PCPs with efficient verifiers
• Query-efficient dictatorship testing with perfect completeness
• The quest for strong inapproximability results with perfect completeness
• Imperfect gaps in Gap-ETH and PCPs
• An improved dictatorship test with perfect completeness
• Three‐query PCPs with perfect completeness over non‐Boolean domains
• STACS 2005
• Small PCPs with low query complexity
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Designated-verifier SNARGs with one group element

This page was built for publication: Query efficient PCPs with perfect completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002760)