On Separation between the Degree of a Boolean Function and the Block Sensitivity.

Nikolay V. Proskurin

Published in: CoRR (2021)

Keyphrases

boolean functions
uniform distribution
relevant variables
pseudo boolean functions
membership queries
read once formulas
functional properties
learning algorithm
lower bound
upper bound
multi valued