Learning juntas

DOI10.1145/780542.780574MaRDI QIDQ3581270zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780574

Mathematics Subject Classification ID

Boolean functions (06E30) Computational learning theory (68Q32)

Recommendations

• Learning functions of \(k\) relevant variables
• On the Fourier spectrum of symmetric Boolean functions
• Parameterized Learnability of k-Juntas and Related Problems

Cited in

(28)

• Parameterized learnability of juntas
• Learning functions of \(k\) relevant variables
• Learning general sparse additive models from point queries in high dimensions
• An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product
• A exact quantum learning algorithm for the 2-junta problem in constant time
• An exact quantum algorithm for the 2-junta problem
• Inferring Boolean functions via higher-order correlations
• On PAC learning algorithms for rich Boolean function classes
• Complexity of approximation of functions of few variables in high dimensions
• The complexity of properly learning simple concept classes
• On two continuum armed bandit problems in high dimensions
• An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables
• An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
• BKW meets Fourier new algorithms for LPN with sparse parities
• Parameterized Learnability of k-Juntas and Related Problems
• Application of a generalization of Russo's formula to learning from multiple random oracles
• Pseudorandom functions: three decades later
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• The Limitations of Optimization from Samples
• On the modulo degree complexity of Boolean functions
• Testing juntas
• Approximation of functions of few variables in high dimensions
• An exact quantum logarithmic time algorithm for the 3-junta problem
• On the degree of Boolean functions as polynomials over \(\mathbb{Z}_m\)
• Consistency checking problems: a gateway to parameterized sample complexity
• On learning embedded midbit functions
• Performance analysis of a greedy algorithm for inferring Boolean functions
• On the Fourier spectrum of symmetric Boolean functions

This page was built for publication: Learning juntas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581270)