Boolean formulas are hard to learn for most gate bases

DOI10.1007/3-540-46769-6_25MaRDI QIDQ4955320zbMATH OpenFDO

Authors Víctor Dalmau

Publication date 24 July 2000

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

Full work available at URL https://doi.org/10.1007/3-540-46769-6_25

zbMATH Keywords

Boolean formulasPAC-predictable even

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Cryptography (94A60)

Recommendations

• A dichotomy theorem for learning quantified Boolean formulas
• Learning Boolean read-once formulas over generalized bases
• Algorithmic Learning Theory
• Learning Boolean formulas

Cited in

(14)

• Learnability of quantified formulas.
• A dichotomy theorem for learning quantified Boolean formulas
• Learning Boolean functions with queries
• Cryptographic limitations on learning Boolean formulae and finite automata
• Derandomized learning of Boolean functions
• Learning rule representations from Boolean data
• GA-based learning of \(k\text{DNF}_n^s\) Boolean formulas
• PAC meditation on Boolean formulas
• Derandomized learning of Boolean functions over finite abelian groups
• Algorithmic Learning Theory
• Exact learning of formulas in parallel
• Boolean autoencoders and hypercube clustering complexity
• A note on the complexity of Boolean concepts
• Learning Boolean specifications

This page was built for publication: Boolean formulas are hard to learn for most gate bases

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