On the decision tree complexity of threshold functions

DOI10.1007/s00224-022-10084-xOpenAlexW4293250543WikidataQ113906002 ScholiaQ113906002MaRDI QIDQ2095465

Vladimir V. Podolskii, Anastasiya Chistopolskaya

Publication date: 16 November 2022

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-022-10084-x

zbMATH Keywords

lower bounddecision treegranularitythreshold functionparity decision tree

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Circuits, networks (94Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Tight bounds for the multiplicative complexity of symmetric functions
• On the parity complexity measures of Boolean functions
• On computing majority by comparisons
• From discrepancy to majority
• Complexity measures and decision tree complexity: a survey.
• Decision trees with Boolean threshold queries
• On the structure of Boolean functions with small spectral norm
• The Relationship between Multiplicative Complexity and Nonlinearity
• Improved Garbled Circuit: Free XOR Gates and Applications
• Circuit Complexity and Multiplicative Complexity of Boolean Functions
• Spectral analysis of Boolean functions as a graph eigenvalue problem
• Communication Complexity
• Analysis of Boolean Functions
• Computing Blindfolded: New Developments in Fully Homomorphic Encryption
• Fourier Sparsity of GF(2) Polynomials
• Testing Fourier Dimensionality and Sparsity

This page was built for publication: On the decision tree complexity of threshold functions