Lower bounds for linear decision trees with bounded weights

DOI10.1007/978-3-662-46078-8_34zbMATH Open1432.68167OpenAlexW2237485987MaRDI QIDQ5175129FDOQ5175129

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

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

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)

Cited In (7)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds for linear decision trees via an energy complexity argument

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)