Improved Bounds for Testing Juntas
From MaRDI portal
Publication:3541805
DOI10.1007/978-3-540-85363-3_26zbMath1159.68008OpenAlexW1598302191MaRDI QIDQ3541805
Publication date: 27 November 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_26
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
An adaptivity hierarchy theorem for property testing ⋮ An optimal tester for \(k\)-linear ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ An optimal tester for \(k\)-Linear ⋮ On Active and Passive Testing ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Property testing lower bounds via communication complexity ⋮ Testing Juntas: A Brief Survey ⋮ Unnamed Item ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ Almost optimal distribution-free junta testing ⋮ Local correction with constant error rate ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities