A lower bound for testing juntas

DOI10.1016/j.ipl.2004.01.023zbMath1178.68668OpenAlexW2074868939MaRDI QIDQ2390270

Hana Chockler, Dan Gutfreund

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.01.023

zbMATH Keywords

computational complexityBoolean functionsrandomized algorithmsproperty testing

Mathematics Subject Classification ID

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

Related Items (11)

Approximating the distance to monotonicity of Boolean functions ⋮ On Active and Passive Testing ⋮ Local correction of juntas ⋮ Quantum algorithms for learning and testing juntas ⋮ Property testing lower bounds via communication complexity ⋮ Testing Juntas: A Brief Survey ⋮ Testing by Implicit Learning: A Brief Survey ⋮ Unnamed Item ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ Almost optimal distribution-free junta testing ⋮ Local correction with constant error rate

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Self-testing/correcting with applications to numerical problems
• A sublinear bipartiteness tester for bounded degree graphs
• Testing k-colorability
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing monotonicity

This page was built for publication: A lower bound for testing juntas