Analysis of Boolean functions

Analysis of Boolean functions studies real-valued functions on a Boolean hypercube using Fourier analysis, probability theory, and combinatorics.

Table of contents

Boolean hypercube ( ${- 1, 1}^{n}$ )

The Boolean hypercube is the set

{- 1, 1}^{n}

, or equivalently

{0, 1}^{n}

. Two vertices are adjacent when they differ in exactly one coordinate.

Edge boundary in a graph ( $\partial_{e} A$ )

The edge boundary of a vertex set

A

consists of graph edges with exactly one endpoint in

A

. In a

d

-regular graph,

∣ \partial_{e} A ∣ = d ∣ A ∣ - 2 e (A),

where

e (A)

counts edges with both endpoints in

A

.

Edge-isoperimetric inequality in the discrete cube

For

A \subseteq {0, 1}^{n}

,

∣ \partial_{e} A ∣ \geq ∣ A ∣ lo g_{2} \frac{2 ^{n}}{∣ A ∣} .

Equivalently,

A

spans at most

\frac{1}{2} ∣ A ∣ lo g_{2} ∣ A ∣

cube edges. Induction on the dimension and concavity of binary entropy prove the inequality.

Binary entropy function ( $H_{2} (x)$ )

The binary entropy function is

H_{2} (x) = - x lo g_{2} x - (1 - x) lo g_{2} (1 - x) .

It is concave on

[0, 1]

and satisfies

H_{2} (x) \geq 2 x

for

0 \leq x \leq 1/2

by comparison with the chord from

(0, 0)

to

(1/2, 1)

.

Boolean function

A Boolean function is a function on a Boolean hypercube, often with codomain

{- 1, 1}

or

{0, 1}

.

Monotone Boolean function

A Boolean function

f : {0, 1}^{n} \to {0, 1}

is monotone when

x_{i} \leq y_{i}

for every

i

implies

f (x) \leq f (y)

.

Fourier-Walsh transform

For

f : {- 1, 1}^{n} \to R

, the characters

χ_{S} (x) = \prod_{i \in S} x_{i}

form an orthonormal basis, and the Fourier-Walsh expansion is

f = \sum_{S \subseteq [n]} f (S) χ_{S}, f (S) = E [f χ_{S}] .

Walsh character ( $χ_{S}$ )

For

S \subseteq [n]

, the Walsh character on the Boolean hypercube is

χ_{S} (x) = \prod_{i \in S} x_{i}

, equivalently

(- 1)^{\sum_{i \in S} x_{i}}

in the zero-one convention.

p-biased product measure ( $μ_{p}$ )

Under the

p

-biased product measure

μ_{p}

on

{- 1, 1}^{n}

, the coordinates are independent random variables with

P (x_{i} = - 1) = p

and

P (x_{i} = 1) = 1 - p

μ = 1 - 2 p

,

σ = 2 p (1 - p)

, and

ϕ_{i} = (x_{i} - μ) / σ

, the products

ϕ_{S} = \prod_{i \in S} ϕ_{i}

form the

p

-biased Fourier basis.

p-biased Fourier coefficient ( $f_{p} (S)$ )

The

p

-biased Fourier coefficient of

f

at

S

is

f_{p} (S) = E_{μ_{p}} [f ϕ_{S}]

.

Discrete derivative of a Boolean function ( $D_{i} f$ )

On the unbiased cube, the discrete derivative is

D_{i} f (x) = \frac{f ( x ^{i \to 1} ) - f ( x ^{i \to - 1} )}{2} = \sum_{S ∋ i} f (S) χ_{S ∖ {i}} (x) .

For the p-biased product measure, the normalization factor is

σ /2

.

Influence of a variable ( $Inf_{i} (f)$ )

The influence of coordinate

i

is

Inf_{i} (f) = ∥ D_{i} f ∥_{2}^{2}

. For a Boolean-valued function on the unbiased cube, it is the probability that flipping coordinate

i

changes the function value.

Total influence ( $I (f)$ )

The total influence is

I (f) = \sum_{i} Inf_{i} (f) = \sum_{S \subseteq [n]} ∣ S ∣ f (S)^{2} .

Margulis-Russo formula

For the indicator

f

of a monotone family under a p-biased product measure, the Margulis-Russo formula identifies the derivative of

E_{μ_{p}} f

with the suitably normalized total influence of

f

.

Noise operator on the Boolean hypercube ( $T_{ρ}$ )

The noise operator averages

f (y)

over a random

y

correlated with

x

by

ρ

. It acts diagonally on the Fourier-Walsh transform:

T_{ρ} f = \sum_{S} ρ^{∣ S ∣} f (S) χ_{S} .

Noise stability ( $Stab_{ρ} (f)$ )

The noise stability is

Stab_{ρ} (f) = ⟨ f, T_{ρ} f ⟩ = \sum_{S} ρ^{∣ S ∣} f (S)^{2} .

Linear Fourier weight ( $W_{1} (f)$ )

The linear Fourier weight is

W_{1} (f) = \sum_{∣ S ∣ = 1} f (S)^{2}

.

Junta

J

-junta is a function whose value depends only on coordinates indexed by

J

. A

k

-junta depends on at most

k

coordinates.

Friedgut junta inequality

If

f : {- 1, 1}^{n} \to {- 1, 1}

satisfies

∥ f^{\leq k} ∥_{2}^{2} \geq 1 - ε

, then it has a real-valued

J

-junta approximation

g

with

∥ f - g ∥_{2}^{2} \leq 2 ε

and

∣ J ∣ \leq \frac{3 ^{2 k} I ( f ) ^{3}}{ε ^{2}} .

Friedgut junta theorem

For every

ε > 0

, a Boolean function

f

has an

exp (O (I (f) / ε))

-junta approximation with squared

L^{2}

error at most

2 ε

.

Nisan-Szegedy junta theorem

Every Boolean function of degree at most

k

is a

k 2^{k - 1}

Quasirandom Boolean function

A Boolean function

f : {0, 1}^{n} \to {0, 1}

is

(ε, p, r)

-quasirandom when conditioning any set of at most

r

coordinates to any values changes its

μ_{p}

-expectation by at most

ε

.

Regularity lemma for Boolean functions

For every

ε, p, r, δ

, there is

T

such that every Boolean function has a set

J

with

∣ J ∣ \leq T

for which a

μ_{p}

-random restriction on

J

leaves an

(ε, p, r)

-quasirandom function with probability at least

1 - δ

.

Bonami lemma

The Bonami lemma states that a function of Fourier degree at most

k

satisfies

∥ f ∥_{4} \leq 3^{k /2} ∥ f ∥_{2}

.

Hypercontractive inequality on the Boolean hypercube

One form of the hypercontractive inequality is

∥ T_{1/ 3} f ∥_{4} \leq ∥ f ∥_{2}

, where

T_{ρ}

is the noise operator on the Boolean hypercube.

Anticoncentration of a low-degree function

If a nonzero function on the Boolean hypercube has degree at most

k

, then its support has measure at least

2^{- k}

. This sharp bound follows by induction on the dimension.

Arrow theorem

Arrow's theorem says that a rank-order voting system with at least three alternatives cannot simultaneously satisfy unrestricted preferences, unanimity, independence of irrelevant alternatives, and absence of a dictator.

Condorcet paradox

The Condorcet paradox is a cycle in collective pairwise preferences even though each individual voter's preference is transitive.

Invariance principle for a low-degree multilinear polynomial

Let

X_{i}

and

Y_{i}

be independent, centered, variance-one random variables with vanishing third moments and fourth moments at most

9

. If

f

is multilinear of degree at most

k

and

∥ ψ^{(4)} ∥_{\infty} \leq M

, then

∣ E ψ (f (X)) - E ψ (f (Y)) ∣ \leq \frac{M}{12} 9^{k} \sum_{i} Inf_{i} (f)^{2} .

Lindeberg replacement method

The Lindeberg replacement method compares functions of two independent random vectors by replacing their coordinates one at a time. Matching moments cancel the corresponding terms in a Taylor expansion.

 Ancestors (4)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Analysis of Boolean functions by

Wikipedia Bot  1

Analysis of Boolean functions is a field of study in mathematics and computer science that focuses on the properties and behaviors of Boolean functions, which are functions that take binary inputs (typically 0s and 1s) and produce binary outputs. This area of analysis is particularly useful in theoretical computer science, combinatorics, and various applications in machine learning, economics, and social choice theory.

 Read the full article

  See all articles in the same topic Create my own version