On the computational power of Boolean decision lists

DOI10.1007/S00037-005-0203-0MaRDI QIDQ853647zbMATH OpenOpenAlexFDO

Authors Matthias Krause

Publication date 17 November 2006

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-005-0203-0

zbMATH Keywords

lower boundslearnabilityDecision lists

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 2086400
• Decision lists and related classes of Boolean functions
• Decision lists and related Boolean functions
• On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
• On the size of binary decision diagrams representing Boolean functions
• On the power of choice for Boolean functions
• The complexity hierarchy of Boolean bases
• scientific article; zbMATH DE number 426344
• On the complexity of restrictions of Boolean functions
• On complexity of a particular Boolean functions class

Cited in

(14)

• Approximate degree and the complexity of depth three circuits
• scientific article; zbMATH DE number 2086400 (Why is no real title available?)
• Lower bounds for linear decision lists
• A lifting theorem with applications to symmetric functions
• Hardness Characterisations and Size-width Lower Bounds for QBF Resolution
• Decision lists and related Boolean functions
• A short list of equalities induces large sign-rank
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Decision lists and related classes of Boolean functions
• Hardness amplification and the approximate degree of constant-depth circuits
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Decision List Compression by Mild Random Restrictions
• A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
• No Efficient Disjunction or Conjunction of Switch-Lists

This page was built for publication: On the computational power of Boolean decision lists

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