On separation between the degree of a Boolean function and the block sensitivity
From MaRDI portal
Publication:2117108
DOI10.1007/978-3-030-79416-3_25OpenAlexW3176700553MaRDI QIDQ2117108
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2101.08600
Cites Work
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- Polynomials with two values
- On the degree of Boolean functions as real polynomials
- Perceptrons, PP, and the polynomial hierarchy
- Complexity measures and decision tree complexity: a survey.
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities
- Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
- Properties and applications of boolean function composition
- Automata, Languages and Programming
- A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
This page was built for publication: On separation between the degree of a Boolean function and the block sensitivity
