Settling the Query Complexity of Non-adaptive Junta Testing

DOI10.1145/3213772zbMath1426.68295OpenAlexW2608070467MaRDI QIDQ4625661

Xi Chen, Erik Waingarten, Jinyu Xie, Li-Yang Tan, 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

adaptivityproperty testingjuntas

Mathematics Subject Classification ID

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

Related Items

Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Testing Boolean Functions Properties