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

(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)