Adaptivity helps for testing juntas

DOI10.4230/LIPICS.CCC.2015.264MaRDI QIDQ4601832zbMATH OpenFDO

Authors

Publication date 24 January 2018

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2015.264

zbMATH Keywords

adaptivityjuntasproperty testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Recommendations

• Settling the query complexity of non-adaptive junta testing
• Settling the query complexity of non-adaptive junta testing
• Improved Bounds for Testing Juntas

Cited in

(10)

• An adaptivity hierarchy theorem for property testing
• Improved Bounds for Testing Juntas
• Settling the query complexity of non-adaptive junta testing
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Settling the query complexity of non-adaptive junta testing
• Testing juntas
• Approximating the distance to monotonicity of Boolean functions
• Direct sum and partitionability testing over general groups
• New statistical and computational results for learning junta distributions

This page was built for publication: Adaptivity helps for testing juntas

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