scientific article; zbMATH DE number 1775415

MaRDI QIDQ4542548zbMATH OpenFDO

Authors Luca Trevisan

Publication date 17 September 2002

zbMATH Keywords

amortized query bits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cited in

(13)

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

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)