Publisher: arXiv, 2011. - 150 pages.
The goal of this set of lectures is to combine two seemingly unrelated topics:
- The study of Boolean functions, a field particularly active in computer science;
- Some models in statistical physics, mostly percolation.
The link between these two fields can be loosely explained as follows: a percolation configuration is built out of a collection of i.i.d "bits" which determines whether the corresponding edges, sites, or blocks are present or absent. In that respect, any event conceing percolation can be seen as a Boolean function whose input are precisely these "bits".
Over the last 20 years, mainly thanks to the computer science community, a very rich structure has emerged conceing the properties of Boolean functions. The first part of this course will be devoted to a description of some of the main achievements in this field. In some sense one can say, although this is an exaggeration, that computer scientists are mostly interested in the stability or robustness of Boolean functions. As we will see later in this course, the Boolean functions which "encode" large scale properties of critical percolation will tu out to be very sensitive to small perturbations. This phenomenon corresponds to what we will call noise sensitivity. Hence, the Boolean functions one wishes to describe here are in some sense orthogonal to the Boolean
functions one encounters, ideally, in computer science. Remarkably, it tus out that the tools developed by the computer science community to capture the properties and stability of Boolean functions are also suitable for the study of noise sensitive functions. This is why it is worth us first spending some time on the general properties of Boolean functions.
The goal of this set of lectures is to combine two seemingly unrelated topics:
- The study of Boolean functions, a field particularly active in computer science;
- Some models in statistical physics, mostly percolation.
The link between these two fields can be loosely explained as follows: a percolation configuration is built out of a collection of i.i.d "bits" which determines whether the corresponding edges, sites, or blocks are present or absent. In that respect, any event conceing percolation can be seen as a Boolean function whose input are precisely these "bits".
Over the last 20 years, mainly thanks to the computer science community, a very rich structure has emerged conceing the properties of Boolean functions. The first part of this course will be devoted to a description of some of the main achievements in this field. In some sense one can say, although this is an exaggeration, that computer scientists are mostly interested in the stability or robustness of Boolean functions. As we will see later in this course, the Boolean functions which "encode" large scale properties of critical percolation will tu out to be very sensitive to small perturbations. This phenomenon corresponds to what we will call noise sensitivity. Hence, the Boolean functions one wishes to describe here are in some sense orthogonal to the Boolean
functions one encounters, ideally, in computer science. Remarkably, it tus out that the tools developed by the computer science community to capture the properties and stability of Boolean functions are also suitable for the study of noise sensitive functions. This is why it is worth us first spending some time on the general properties of Boolean functions.