1. Boolean functions and key concepts; 2. Percolation in a nutshell; 3. Sharp thresholds and the critical point; 4. Fourier analysis of Boolean functions; 5. Hypercontractivity and its applications; 6. First evidence of noise sensitivity of percolation; 7. Anomalous fluctuations; 8. Randomized algorithms and noise sensitivity; 9. The spectral sample; 10. Sharp noise sensitivity of percolation; 11. Applications to dynamical percolation; 12. For the connoisseur; 13. Further directions and open problems.
This is the first book to cover the theory of noise sensitivity of Boolean functions with particular emphasis on critical percolation.
Christophe Garban is a professor of mathematics at Université Lyon I, France. Jeffrey Steif is a Professor of Mathematical Sciences at Chalmers University of Technology, Gothenburg, Sweden.
'Presented in an orderly, accessible manner, this book provides an
excellent exposition of the general theory of noise sensitivity and
its beautiful and deep manifestation in two dimensional critical
percolation. The authors, both of whom are major contributors to
the theory, have produced a very thoughtful work, bringing the
intuition and motivations first. Noise sensitivity is a natural
concept that recently found diverse applications, ranging from
quantum computation and complexity theory to statistical physics
and social choice. Two dimensional critical percolation is a
striking and canonical random object. The book elegantly unfolds
the story of integrating the general theory of noise sensitivity
into a concrete study, allowing for a new understanding of the
percolation process.' Itai Benjamini, Weizmann Institute of
Science, Israel
'This book is about a beautiful mathematical story, centered around
the wonderful, ever-changing theory of probability and rooted in
questions of physics and computer science. Christophe Garban and
Jeffrey Steif, both heroes of the research advances described in
the book, tell the story and lucidly explain the underlying
probability theory, combinatorics, analysis, and geometry - from a
very basic to a state-of-the-art level. The authors make great
choices on what to explain and include in the book, leaving the
readers with perfect conceptual understanding and technical tools
to go beyond the text and, at the same time, with much appetite for
learning and exploring even further.' Gil Kalai, Hebrew
University
'Boolean functions map many bits to a single bit. Percolation is
the study of random configurations in the lattice and their
connectivity properties. These topics seem almost disjointed -
except that the existence of a left-to-right crossing of a square
in the 2D lattice is a Boolean function of the edge variables. This
observation is the beginning of a magical theory, developed by Oded
Schramm and his collaborators, in particular Itai Benjamini, Gil
Kalai, Gabor Pete, and the authors of this wonderful book. The book
expertly conveys the excitement of the topic; connections with
discrete Fourier analysis, hypercontractivity, randomized
algorithms, dynamical percolation, and more are explained
rigorously, yet without excessive formality. Numerous open problems
point the way to the future.' Yuval Peres, Principal Researcher,
Microsoft
'Without hesitation, I can recommend this monograph to any
probabilist who has considered venturing into the domain of noise
sensitivity of Boolean functions. All fundamental concepts of the
field such as influence or noise sensitivity are explained in a
refreshingly accessible way, so that only a minimal understanding
of probability theory is assumed. The authors succeed in guiding
the reader gently from the basics to the most recent seminal
developments in Fourier analysis of Boolean functions,
familiarizing her or him with all the modern machinery along the
way.' Christian Hirsch, Mathematical Reviews
'Considerable effort was made to make the book as thorough and
concise as possible but still readable and friendly. … It is clear
that it will turn out to be the 'go to' source for studying the
subject of noise sensitivity of Boolean functions.' Eviatar B.
Procaccia, Bulletin of the American Mathematical Society
|
Ask a Question About this Product More... |
|
