Parameterized learnability of juntas

DOI10.1016/J.TCS.2009.07.003zbMath1194.68186OpenAlexW2021964998MaRDI QIDQ1034613

Johannes Köbler, V. Arvind, Wolfgang Lindner

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.003

zbMATH Keywords

computational complexitylearning theory

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (1)

A multi-parameter analysis of hard problems on deterministic finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Exploring learnability between exact and PAC
• Oracles and queries that are sufficient for exact learning
• Parametrized complexity theory.
• 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
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Parameterized learnability of juntas