On the Decision Tree Complexity of Threshold Functions

DOI10.1007/978-3-030-50026-9_14OpenAlexW3035812899MaRDI QIDQ5042240

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

lower bounddecision treegranularitythreshold functionparity decision tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• On the parity complexity measures of Boolean functions
• From discrepancy to majority
• Complexity measures and decision tree complexity: a survey.
• Decision trees with Boolean threshold queries
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Structure of Protocols for XOR Functions
• Communication Complexity
• Analysis of Boolean Functions

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