Lower bounds for linear decision trees with bounded weights

DOI10.1007/978-3-662-46078-8_34MaRDI QIDQ5175129zbMATH OpenOpenAlexFDO

Authors Kei Uchizawa, Eiji Takimoto

Publication date 20 February 2015

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

Full work available at URL https://doi.org/10.1007/978-3-662-46078-8_34

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• Lower bounds for linear decision trees via an energy complexity argument
• scientific article; zbMATH DE number 176776
• On the size of depth-two threshold circuits for the inner product mod 2 function
• Lower bounds for linear decision lists
• Decision trees with Boolean threshold queries

Cited in

(7)

• Lower bounds for linear decision trees via an energy complexity argument
• Lower bounds on probabilistic linear decision trees
• Lower bounds for linear decision lists
• On (simple) decision tree rank
• Linear threshold functions in decision lists, decision trees, and depth-2 circuits
• scientific article; zbMATH DE number 176776 (Why is no real title available?)
• scientific article; zbMATH DE number 910895 (Why is no real title available?)

This page was built for publication: Lower bounds for linear decision trees with bounded weights

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