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 t...

Full description

Saved in:
Bibliographic Details
Main Authors: Ana Salagean, Percy Reyes-Paredes
Format: Conference Proceeding
Language:English
Subjects:
Boolean functions
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.