scientific article; zbMATH DE number 1775415

zbMATH Open1029.68556MaRDI QIDQ4542548FDOQ4542548

Authors: Luca Trevisan 

Publication date: 17 September 2002

Title of this publication is not available (Why is that?)

Recommendations

• A PCP characterization of NP with optimal amortized query complexity
• STACS 2005
• Towards an optimal query efficient PCP?
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Simple analysis of graph tests for linearity and PCP

zbMATH Keywords

amortized query bits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (11)

• A PCP characterization of NP with optimal amortized query complexity
• Interactive and probabilistic proof-checking
• 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
• Query-efficient dictatorship testing with perfect completeness
• Linear-consistency testing.
• Simple analysis of graph tests for linearity and PCP
• STACS 2005
• A self-tester for linear functions over the integers with an elementary proof of correctness
• On non-optimally expanding sets in Grassmann graphs
• Towards an optimal query efficient PCP?

This page was built for publication:

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