On the decision tree complexity of threshold functions

DOI10.1007/S00224-022-10084-XMaRDI QIDQ2095465zbMATH OpenOpenAlexWikidataFDO

Authors Anastasiya Chistopolskaya, Vladimir V. Podolskii

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

decision treelower boundgranularitythreshold functionparity decision tree

Mathematics Subject Classification ID

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

Recommendations

• Decision trees with Boolean threshold queries
• On the parity complexity measures of Boolean functions
• Average-Case Lower Bounds for Noisy Boolean Decision Trees
• On the power of parity queries in Boolean decision trees
• scientific article; zbMATH DE number 176776

Cites work

• scientific article; zbMATH DE number 176776 (Why is no real title available?)
• Analysis of Boolean Functions
• Boolean function complexity. Advances and frontiers.
• Circuit complexity and multiplicative complexity of Boolean functions
• Communication Complexity
• Complexity measures and decision tree complexity: a survey.
• Computing Blindfolded: New Developments in Fully Homomorphic Encryption
• Decision trees with Boolean threshold queries
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• From discrepancy to majority
• Improved Garbled Circuit: Free XOR Gates and Applications
• On computing majority by comparisons
• On the parity complexity measures of Boolean functions
• Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent
• Spectral analysis of Boolean functions as a graph eigenvalue problem
• Testing Fourier dimensionality and sparsity
• The relationship between multiplicative complexity and nonlinearity
• Tight bounds for the multiplicative complexity of symmetric 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 Q2095465)