Parameterized Learnability of k-Juntas and Related Problems

DOI10.1007/978-3-540-75225-7_13MaRDI QIDQ3520054zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Wolfgang Lindner, 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

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

Recommendations

• Parameterized learnability of juntas
• Learning juntas
• Learning juntas in the presence of noise

Cites work

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

Cited in

(7)

• Parameterized learnability of juntas
• Application of a generalization of Russo's formula to learning from multiple random oracles
• Learning juntas
• On the exact learnability of graph parameters: the case of partition functions
• Improved learning of \(k\)-parities
• The parameterized complexity of learning monadic second-order logic
• On the Fourier spectrum of symmetric Boolean functions

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

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