Testing Juntas: A Brief Survey

DOI10.1007/978-3-642-16367-8_4zbMath1308.68148OpenAlexW1479783912MaRDI QIDQ4933362

Eric Blais

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_4

zbMATH Keywords

survey paper

Mathematics Subject Classification ID

Computational learning theory (68Q32) Randomized algorithms (68W20)

Related Items (1)

Non-interactive proofs of proximity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing juntas
• Selection of relevant features and examples in machine learning
• The jackknife estimate of variance
• Self-testing/correcting with applications to numerical problems
• Learning functions of \(k\) relevant variables
• Learning in the presence of finitely or infinitely many irrelevant attributes
• A lower bound for testing juntas
• Quantum algorithms for learning and testing juntas
• Linearity testing in characteristic two
• Property testing and its connection to learning and approximation
• Improved Bounds for Testing Juntas
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Testing Basic Boolean Formulae
• Testing by Implicit Learning: A Brief Survey
• Query-Efficient Dictatorship Testing with Perfect Completeness
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Testing juntas nearly optimally
• Quantum lower bounds by polynomials
• Algorithmic Aspects of Property Testing in the Dense Graphs Model

This page was built for publication: Testing Juntas: A Brief Survey