Lower bounds for linear decision lists

DOI10.4086/CJTCS.2020.001MaRDI QIDQ4988300zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh

Publication date 14 May 2021

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1901.05911

zbMATH Keywords

decision listslinear threshold functionsthreshold circuits

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bounds for linear decision trees with bounded weights
• scientific article; zbMATH DE number 176776
• Lower bounds on learning decision lists and trees
• Lower bounds for linear decision trees via an energy complexity argument
• Decision lists and related classes of Boolean functions

Cites work

• Harmonic Analysis of Polynomial Threshold Functions
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 1008380 (Why is no real title available?)
• scientific article; zbMATH DE number 5937160 (Why is no real title available?)
• On the computational power of Boolean decision lists
• Optimal numberings and isoperimetric problems on graphs
• Some intersection theorems for ordered sets and graphs

Cited in

(8)

• Lower bounds for some decision problems over \(C\)
• Proof complexity of symbolic QBF reasoning
• Decision lists and related classes of Boolean functions
• scientific article; zbMATH DE number 1008380 (Why is no real title available?)
• Lower bounds for monotonic list labeling
• Decision List Compression by Mild Random Restrictions
• Lower bounds for linear decision trees with bounded weights
• Linear threshold functions in decision lists, decision trees, and depth-2 circuits

This page was built for publication: Lower bounds for linear decision lists

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