Learning juntas

DOI10.1145/780542.780574zbMath1192.68393OpenAlexW2295021037MaRDI QIDQ3581270

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

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

Related Items (22)

The Limitations of Optimization from Samples ⋮ Performance analysis of a greedy algorithm for inferring Boolean functions ⋮ A exact quantum learning algorithm for the 2-junta problem in constant time ⋮ Exact learning of juntas from membership queries ⋮ Testing juntas ⋮ An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables ⋮ Approximation of functions of few variables in high dimensions ⋮ An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product ⋮ Complexity of approximation of functions of few variables in high dimensions ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ BKW meets Fourier new algorithms for LPN with sparse parities ⋮ The complexity of properly learning simple concept classes ⋮ An exact quantum algorithm for the 2-junta problem ⋮ Inferring Boolean functions via higher-order correlations ⋮ Learning general sparse additive models from point queries in high dimensions ⋮ On the Fourier spectrum of symmetric Boolean functions ⋮ On the modulo degree complexity of Boolean functions ⋮ Unnamed Item ⋮ Parameterized learnability of juntas ⋮ Pseudorandom Functions: Three Decades Later ⋮ On two continuum armed bandit problems in high dimensions ⋮ An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product

This page was built for publication: Learning juntas