Settling the query complexity of non-adaptive junta testing

DOI10.1145/3213772MaRDI QIDQ4625661zbMATH OpenOpenAlexFDO

Authors Xi Chen, Li-Yang Tan, Erik Waingarten, Jinyu Xie, Rocco A. Servedio

Publication date 25 February 2019

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7528/

zbMATH Keywords

adaptivityjuntasproperty testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

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

Cited in

(10)

• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• A lower bound for testing juntas
• Quantum and classical query complexities for generalized Deutsch-Jozsa problems
• Improved Bounds for Testing Juntas
• Adaptivity helps for testing juntas
• Testing Boolean functions properties
• Settling the query complexity of non-adaptive junta testing
• scientific article; zbMATH DE number 6292744 (Why is no real title available?)
• Approximating the distance to monotonicity of Boolean functions
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity

This page was built for publication: Settling the query complexity of non-adaptive junta testing

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