Boolean functions are perhaps the most basic objects of study in theoretical computer
science. They also arise in other areas of mathematics, including combinatorics, statistical …

We prove an inequality on decision trees on monotonic measures which generalizes the
OSSS inequality on product spaces. As an application, we use this inequality to prove a …

It is shown that a Gromov hyperbolic geodesic metric space X with bounded growth at some
scale is roughly quasi-isometric to a convex subset of hyperbolic space. If one is allowed to …

Percolation models describe the inside of a porous material. The theory emerged timidly in
the middle of the twentieth century before becoming one of the major objects of interest in …

Phase transitions are a central theme of statistical mechanics, and of probability more
generally. Lattice spin models represent a general paradigm for phase transitions in finite …

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean
function f, deg (f)= O (adeg (f)^ 2): The degree of f is at most quadratic in the approximate …

A Brief Introduction to Fourier Analysis on the Boolean Cube Page 1 Theory OF Computing
Library Graduate Surveys, TCGS 1 (2008), pp. 1–20 http://theoryofcomputing.org A Brief …

We consider upper level sets of the Gaussian free field (GFF) on Z d, for d≥ 3, above a
given real-valued height parameter h. As h varies, this defines a canonical percolation …

Is there a general theorem that tells us when we can hope for exponential speedups from
quantum algorithms, and when we cannot? In this paper, we make two advances toward …

This is a graduate-level introduction to the theory of Boolean functions, an exciting area lying
on the border of probability theory, discrete mathematics, analysis, and theoretical computer …