Efficient Sample Extractors for Juntas with Applications

DOI10.1007/978-3-642-22006-7_46zbMath1334.68297OpenAlexW2179884588MaRDI QIDQ3012831

David García-Soriano, Sourav Chakraborty, Arie Matsliah

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_46

zbMATH Keywords

property testingimplicit learningsample extractors

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (8)

Sampling Correctors ⋮ On one-sided testing affine subspaces ⋮ Almost optimal proper learning and testing polynomials ⋮ An optimal tester for \(k\)-Linear ⋮ Almost Optimal Testers for Concise Representations. ⋮ Property testing lower bounds via communication complexity ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Unnamed Item

Uses Software

• R

Cites Work

• Testing juntas
• Property testing lower bounds via communication complexity
• Nearly Tight Bounds for Testing Function Isomorphism
• Efficiently Testing Sparse GF(2) Polynomials
• Testing Basic Boolean Formulae
• Testing by Implicit Learning: A Brief Survey
• Testing juntas nearly optimally
• Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
• Testing Fourier Dimensionality and Sparsity

This page was built for publication: Efficient Sample Extractors for Juntas with Applications