Testing juntas nearly optimally

From MaRDI portal
Publication:5172708

DOI10.1145/1536414.1536437zbMath1304.68059OpenAlexW2009813398MaRDI QIDQ5172708

Eric Blais

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




Related Items (32)

An adaptivity hierarchy theorem for property testingAn optimal tester for \(k\)-linearReducing Testing Affine Spaces to Testing Linearity of FunctionsApproximating the distance to monotonicity of Boolean functionsInfluence of a Set of Variables on a Boolean FunctionA local decision test for sparse polynomialsAn optimal tester for \(k\)-LinearOn Active and Passive TestingLocal correction of juntasTesting Euclidean SpannersSample-Based High-Dimensional Convexity Testing.Lower Bounds for Testing Computability by Small Width OBDDsEfficient Sample Extractors for Juntas with ApplicationsAlmost Optimal Testers for Concise Representations.Property testing lower bounds via communication complexityTesting Juntas: A Brief SurveyTesting by Implicit Learning: A Brief SurveyInvariance in Property TestingUnnamed ItemOn Approximating the Number of Relevant Variables in a FunctionGaussian bounds for noise correlation of resilient functionsA Canonical Form for Testing Boolean Function PropertiesApproximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query ComplexityAlmost optimal distribution-free junta testingA unified framework for testing linear‐invariant propertiesUnnamed ItemPartially Symmetric Functions Are Efficiently Isomorphism TestableRobust characterizations of k -wise independence over product spaces and related testing resultsUnnamed ItemLocal correction with constant error rateQuantum algorithms for learning symmetric juntas via the adversary boundExponentially improved algorithms and lower bounds for testing signed majorities




This page was built for publication: Testing juntas nearly optimally