On the Decision Tree Complexity of Threshold Functions

DOI10.1007/978-3-030-50026-9_14MaRDI QIDQ5042240zbMATH OpenOpenAlexFDO

Authors Anastasiya Chistopolskaya, Vladimir V. Podolskii

Publication date 19 October 2022

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-50026-9_14

zbMATH Keywords

decision treegranularitylower boundparity decision treethreshold function

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Analysis of Boolean Functions
• Boolean function complexity. Advances and frontiers.
• Communication Complexity
• Complexity measures and decision tree complexity: a survey.
• Decision trees with Boolean threshold queries
• From discrepancy to majority
• scientific article; zbMATH DE number 176776 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On the parity complexity measures of Boolean functions
• Structure of protocols for XOR functions
• Tight complexity lower bounds for integer linear programming with few constraints

Cited in

(2)

• scientific article; zbMATH DE number 7650404 (Why is no real title available?)
• Decision tree complexity and Betti numbers

This page was built for publication: On the Decision Tree Complexity of Threshold Functions

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