Parameterized Learnability of k-Juntas and Related Problems

DOI10.1007/978-3-540-75225-7_13zbMath1142.68381OpenAlexW1579117122MaRDI QIDQ3520054

Wolfgang Lindner, V. Arvind, Johannes Köbler

Publication date: 19 August 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-75225-7_13

zbMATH Keywords

computational complexitylearning theory

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Unnamed Item
• Fast learning of \(k\)-term DNF formulas with queries.
• NP is as easy as detecting unique solutions
• Learning regular sets from queries and counterexamples
• Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
• Occam's razor
• Approximation algorithms for combinatorial problems
• Learning Boolean concepts in the presence of many irrelevant features
• Oracles and queries that are sufficient for exact learning
• Learning juntas
• A theory of the learnable
• Computational limitations on learning from examples
• A Greedy Heuristic for the Set-Covering Problem
• Learning Decision Trees Using the Fourier Spectrum
• On the Fourier spectrum of monotone functions
• Fixed-Parameter Tractability and Completeness I: Basic Results

This page was built for publication: Parameterized Learnability of k-Juntas and Related Problems