Boolean function

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

{- 1, 1}

or

{0, 1}

.

Table of contents

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 - δ

.

 Ancestors (6)

 Incoming links (2)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Boolean function by

Wikipedia Bot  1

A Boolean function is a mathematical function that takes inputs from a set of binary values (typically 0 and 1) and produces a binary output. The function is named after the mathematician and logician George Boole, who developed an algebraic system for logical reasoning. Boolean functions can be represented in various ways, including: 1. **Truth Tables**: A table that lists all possible combinations of input values and the corresponding output.

 Read the full article

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