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

DOI10.1016/J.IPL.2023.106418MaRDI QIDQ6072201zbMATH OpenFDO

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

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)

Recommendations

• Lower bounds for linear decision trees with bounded weights
• Lower bounds for linear decision lists
• Decision lists and related classes of Boolean functions
• Linear-size constant-depth polylog-threshold circuits
• Lower bounds for linear decision trees via an energy complexity argument

Cites work

• scientific article; zbMATH DE number 176776 (Why is no real title available?)
• scientific article; zbMATH DE number 1008380 (Why is no real title available?)
• A short list of equalities induces large sign-rank
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Learning decision trees from random examples
• Lower bounds for linear decision lists
• Lower bounds for linear decision trees with bounded weights
• Majority gates vs. general weighted threshold gates
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists

This page was built for publication: Linear threshold functions in decision lists, decision trees, and depth-2 circuits

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