Consistency checking problems: a gateway to parameterized sample complexity

DOI10.4230/LIPICS.IPEC.2023.18MaRDI QIDQ6926191zbMATH OpenFDO

Authors Robert Ganian, Kirill Simonov

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.18

zbMATH Keywords

fixed-parameter tractabilitysample complexityconsistency checking

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 795584 (Why is no real title available?)
• A theory of the learnable
• Competitive group testing and learning hidden vertex covers with minimum adaptivity
• Computational limitations on learning from examples
• Formal Methods for Components and Objects
• Foundations of machine learning
• Graph theory
• Learnability and the Vapnik-Chervonenkis dimension
• Learning juntas
• Parameterized algorithms
• Parameterized learnability of juntas
• The complexity of properly learning simple concept classes
• The optimal sample complexity of PAC learning
• The splittance of a graph

This page was built for publication: Consistency checking problems: a gateway to parameterized sample complexity

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