On the decision tree complexity of threshold functions
From MaRDI portal
Publication:2095465
DOI10.1007/S00224-022-10084-XOpenAlexW4293250543WikidataQ113906002 ScholiaQ113906002MaRDI QIDQ2095465FDOQ2095465
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
Recommendations
Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx) Circuits, networks (94Cxx)
Cites Work
- Analysis of Boolean Functions
- The relationship between multiplicative complexity and nonlinearity
- Improved Garbled Circuit: Free XOR Gates and Applications
- Communication Complexity
- Boolean function complexity. Advances and frontiers.
- Tight bounds for the multiplicative complexity of symmetric functions
- On computing majority by comparisons
- Circuit complexity and multiplicative complexity of Boolean functions
- Complexity measures and decision tree complexity: a survey.
- Testing Fourier dimensionality and sparsity
- Decision trees with Boolean threshold queries
- Spectral analysis of Boolean functions as a graph eigenvalue problem
- Computing Blindfolded: New Developments in Fully Homomorphic Encryption
- From discrepancy to majority
- Tight complexity lower bounds for integer linear programming with few constraints
- On the parity complexity measures of Boolean functions
- Title not available (Why is that?)
- Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent
- Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
Cited In (2)
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)
