Linear threshold functions in decision lists, decision trees, and depth-2 circuits

DOI10.1016/j.ipl.2023.106418zbMath1529.68099MaRDI QIDQ6072201

Yogesh Dahiya, Karteek Sreenivasaiah, Meena Mahajan, Vignesh K.

Publication date: 12 October 2023

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitydecision treeslinear threshold functionsdepth-2 circuitstree rank

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Majority gates vs. general weighted threshold gates
• Learning decision trees from random examples
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• A Short List of Equalities Induces Large Sign-Rank
• Lower Bounds for Linear Decision Trees with Bounded Weights
• Unnamed Item
• Unnamed Item
• Unnamed Item