This is a very short introductory survey of graph-theoretic properties of Boolean functions.

I don’t know who first studied Boolean functions for their own sake. However, the study of Boolean functions from the graph-theoretic perspective originated in Anna Bernasconi‘s thesis. More detailed presentation of the material can be found in various places. For example, Bernasconi’s thesis (e.g., see [BC]), the nice paper by P. Stanica (e.g., see [S], or his book with T. Cusick), or even my paper with Celerier, Melles and Phillips (e.g., see [CJMP], from which much of this material is literally copied).

For a given positive integer , we may identify a Boolean function

with its support

For each , let denote the set of complements , for , and let denote the complementary Boolean function. Note that

where denotes the complement of in . Let

denote the cardinality of the support. We call a Boolean function *even* (resp., *odd*) if is even (resp., odd). We may identify a vector in with its support, or, if it is more convenient, with the corresponding integer in Let

be the binary representation ordered with least significant bit last (so that, for example, ).

Let denote the $2^n\times 2^n$ Hadamard matrix defined by , for each such that . Inductively, these can be defined by

The *Walsh-Hadamard transform* of is defined to be the vector in whose th component is

where we define as the column vector where the th component is

for .

**Example**

A Boolean function of three variables cannot be bent. Let be defined by:

This is simply the function . It is even because

Here is some Sage code verifying this:

sage: from sage.crypto.boolean_function import * sage: f = BooleanFunction([0,1,0,1,0,1,0,1]) sage: f.algebraic_normal_form() x0 sage: f.walsh_hadamard_transform() (0, -8, 0, 0, 0, 0, 0, 0)

(The Sage method `walsh_hadamard_transform` is off by a sign from the definition we gave.) We will return to this example later.

Let be the *Cayley graph* of :

We shall assume throughout and without further mention that so has no loops. In this case, is an -regular graph having connected components, where

For each vertex , the set of neighbors of is given by

where is regarded as a vector and the addition is induced by the usual vector addition in . Let be the adjacency matrix of , so

**Example:**

Returning to the previous example, we construct its Cayley graph.

First, `attach afsr.sage` from [C] in your Sage session.

sage: flist = [0,1,0,1,0,1,0,1] sage: V = GF(2)ˆ3 sage: Vlist = V.list() sage: f = lambda x: GF(2)(flist[Vlist.index(x)]) sage: X = boolean_cayley_graph(f, 3) sage: X.adjacency_matrix() [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] sage: X.spectrum() [4, 0, 0, 0, 0, 0, 0, -4] sage: X.show(layout="circular")

In her thesis, Bernasconi found a relationship between the spectrum of the Cayley graph ,

(the eigenvalues of the adjacency matrix ) to the Walsh-Hadamard transform . Note that and are related by the equation where . She discovered the relationship

between the spectrum of the Cayley graph of a Boolean function and the values of the Walsh-Hadamard transform of the function. Therefore, the spectrum of , is explicitly computable as an expression in terms of .

**References:**

[BC] A. Bernasconi and B. Codenotti, *Spectral analysis of Boolean functions as a graph eigenvalue problem*, IEEE Trans. Computers 48(1999)345-351.

[CJMP] Charles Celerier, David Joyner, Caroline Melles, David Phillips, *On the Hadamard transform of monotone Boolean functions*, Tbilisi Mathematical Journal, Volume 5, Issue 2 (2012), 19-35.

[S] P. Stanica, *Graph eigenvalues and Walsh spectrum of Boolean functions*, Integers 7(2007)\# A32, 12 pages.

Here’s an excellent video of Pante Stanica on interesting applications of Boolean functions to cryptography (30 minutes):

You must be logged in to post a comment.