Probabilistic estimation of the degree of Boolean functions [Extended abstract]

We propose a probabilistic test for deciding whether the algebraic degree of a Boolean function f is below a certain value k. The test involves picking an affine space of dimension at most k and testing whether the values on f on that space sum up to zero. If deg(f) < k, then f will always pass the test, otherwise it will sometimes pass and sometimes fail the test, depending on which affine space we choose. We commence the study of the probability of failure of this test for functions of degree k or more. For the case when deg(f) = k we prove that the probability is in the interval (0.288788, 0.5). We also compute exhaustively these probabilities for functions in 8 variables.