jellepiepenbrock / boolan

Python package to determine characteristics of Boolean functions [noise sensitivity, expected values, etc.]

---

Boolan (boolean analysis) is a small Python package to determine characteristics of Boolean functions. It uses the fact that Boolean functions can be expressed as multilinear polynomials over a two valued field {1, -1} [1]. Transforming the Boolean functions into this polynomial (which is close to a Fourier transform), exposes all kinds of information about the behavior of the function, which can be gleaned from the Fourier coefficients of the polynomial.

Install

Sage computer algebra environment

Boolan uses the Sage computer algebra environment to do its rewriting. In order to install and make use of Boolan, one first has to install Sage.

Linux and macOS

The easiest and most foolproof way to do this is via Conda Forge. To avoid conflicts, one should make a new environment where Sage is installed. If you don't have Conda, you can get it here.

Add the conda-forge package channel to config

conda config --add channels conda-forge

Make sure everything is up to date

conda update --all

Install Sage in its own Conda environment

conda create -n sage sage

Install Boolan

pip install git+https://github.com/JellePiepenbrock/Boolan

Windows

SageMath on Windows requires a 64-bit version Windows, which is likely on a modern computer. You can download the pre-build SageMath installer for Windows from the github release page. For alternatives, you can have a look at the installation guide. Note that you need to run the Python environment that is bundled with SageMath. You can install Boolan from the inside of the environment, such as the notebook, via this command:

import sys
!{sys.executable} -m pip install git+https://github.com/JellePiepenbrock/Boolan

Read more on the SageMath FAQ.

Features

Boolean functions can be written as polynomials, with -1 coding for True and 1 for False (read that again; the ordering is not a mistake!). The two-input AND function can be expressed like this:

The influence of a certain variable on the ouput is a quantity that could be of interest. It is defined as the sum of the squares of all the coefficients of the terms that contain the variable. The total influence of a function is then the sum of the influences of all the input variables of the function.

We can also calculate the noise sensitivity of the function, given that there is a delta probability that each input bit is flipped by noise.

Examples

Getting the characteristics of a function

The two-input AND function can be analysed in the following way. Note that outputs for rows in the truth table are given in the following order: [11, 10, 01, 00]. This is extended in the obvious way for functions with more inputs.

from boolan.boolan import get_function_characteristics

AND = [-1, 1, 1, 1]
features = get_function_characteristics(AND)

This piece of code will give you the following characteristics of the function:

• Total Influence
• Weights on each order of monomial (3 values in the case of AND)
• Variance
• Noise Sensitivity at noise levels [0.1, 0.2, 0.3, 0.4]

Rewriting to a polynomial

Calling the get_fpolynomial function in the following way gives you a Sage Polynomial object:

>>> get_fpolynomial(AND, 2)
"-1/2*a*b + 1/2*a + 1/2*b + 1/2"

Which matches the polynomial that was given earlier.

References and further reading

1. O'Donnell, R. (2014). Analysis of boolean functions. Cambridge University Press.