Testing juntas nearly optimally
From MaRDI portal
Publication:5172708
DOI10.1145/1536414.1536437zbMath1304.68059OpenAlexW2009813398MaRDI QIDQ5172708
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1536414.1536437
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (32)
An adaptivity hierarchy theorem for property testing ⋮ An optimal tester for \(k\)-linear ⋮ Reducing Testing Affine Spaces to Testing Linearity of Functions ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Influence of a Set of Variables on a Boolean Function ⋮ A local decision test for sparse polynomials ⋮ An optimal tester for \(k\)-Linear ⋮ On Active and Passive Testing ⋮ Local correction of juntas ⋮ Testing Euclidean Spanners ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Efficient Sample Extractors for Juntas with Applications ⋮ Almost Optimal Testers for Concise Representations. ⋮ Property testing lower bounds via communication complexity ⋮ Testing Juntas: A Brief Survey ⋮ Testing by Implicit Learning: A Brief Survey ⋮ Invariance in Property Testing ⋮ Unnamed Item ⋮ On Approximating the Number of Relevant Variables in a Function ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ A Canonical Form for Testing Boolean Function Properties ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ Almost optimal distribution-free junta testing ⋮ A unified framework for testing linear‐invariant properties ⋮ Unnamed Item ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Robust characterizations of k -wise independence over product spaces and related testing results ⋮ Unnamed Item ⋮ Local correction with constant error rate ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities
This page was built for publication: Testing juntas nearly optimally
