On the computational power of Boolean decision lists
DOI10.1007/S00037-005-0203-0zbMATH Open1105.68043OpenAlexW2070053951MaRDI QIDQ853647FDOQ853647
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
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
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)
Cited In (14)
- Approximate degree and the complexity of depth three circuits
- Title not available (Why is that?)
- 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)
