In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
theoretical computer science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, analysis of Boolean functions is the study of real-valued functions on
or
(such functions are sometimes known as
pseudo-Boolean function
In mathematics and optimization, a pseudo-Boolean function is a function of the form
:f: \mathbf^n \to \R,
where is a ''Boolean domain'' and is a nonnegative integer called the arity of the function. A Boolean function is then a special case, wh ...
s) from a spectral perspective.
The functions studied are often, but not always, Boolean-valued, making them
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...
s. The area has found many applications in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
,
social choice theory
Social choice theory is a branch of welfare economics that extends the Decision theory, theory of rational choice to collective decision-making. Social choice studies the behavior of different mathematical procedures (social welfare function, soc ...
,
random graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...
s, and theoretical computer science, especially in
hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems.
Scope
Hardness of approximation complements the study of approximation algorithms by pro ...
,
property testing
Property testing is a field of theoretical computer science, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects.
A ''property testing algorithm ...
, and
PAC learning.
Basic concepts
We will mostly consider functions defined on the domain
. Sometimes it is more convenient to work with the domain
instead. If
is defined on
, then the corresponding function defined on
is
:
Similarly, for us a Boolean function is a
-valued function, though often it is more convenient to consider
-valued functions instead.
Fourier expansion
Every real-valued function
has a unique expansion as a multilinear polynomial:
:
(Note that even if the function is 0-1 valued this is not a sum mod 2, but just an ordinary sum of real numbers.)
This is the
Hadamard transform
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
of the function
, which is the
Fourier transform
In mathematics, the Fourier transform (FT) is an integral transform that takes a function as input then outputs another function that describes the extent to which various frequencies are present in the original function. The output of the tr ...
in the
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
. The coefficients
are known as ''Fourier coefficients'', and the entire sum is known as the ''Fourier expansion'' of
. The functions
are known as ''Fourier characters'', and they form an orthonormal basis for the space of all functions over
, with respect to the inner product
.
The Fourier coefficients can be calculated using an inner product:
:
In particular, this shows that