On Sharp Thresholds of Monotone Properties: Bourgain's Proof Revisited

We give a characterization of vertex-monotone properties with sharp thresholds in a Poisson random geometric graph or hypergraph. As an application we show that a geometric model of random k-SAT exhibits a sharp threshold for satisfiability.

We show that on every product probability space, Boolean functions with small total influences are essentially the ones that are almost measurable with respect to certain natural sub-sigma algebras. This theorem in particular describes the structure of monotone set properties that do not exhibit sharp thresholds. Our result generalizes the core of Friedgut's seminal work [Ehud Friedgut. Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12(4):...

A key fact in the theory of Boolean functions $f : \{0,1\}^n \to \{0,1\}$ is that they often undergo sharp thresholds. For example: if the function $f : \{0,1\}^n \to \{0,1\}$ is monotone and symmetric under a transitive action with $\E_p[f] = \eps$ and $\E_q[f] = 1-\eps$ then $q-p \to 0$ as $n \to \infty$. Here $\E_p$ denotes the product probability measure on $\{0,1\}^n$ where each coordinate takes the value $1$ independently with probability $p$. The fact that symmetric fu...

Threshold phenomena are investigated using a general approach, following Talagrand [Ann. Probab. 22 (1994) 1576--1587] and Friedgut and Kalai [Proc. Amer. Math. Soc. 12 (1999) 1017--1054]. The general upper bound for the threshold width of symmetric monotone properties is improved. This follows from a new lower bound on the maximal influence of a variable on a Boolean function. The method of proof is based on a well-known logarithmic Sobolev inequality on $\{0,1\}^n$. This ne...

We survey the current state of affairs in the study of thresholds and sharp thresholds in random structures on the occasion of the recent proof of the Kahn--Kalai Conjecture by Park and Pham and the fairly recent proof of the satisfiability conjecture for large $k$ by Ding, Sly, and Sun. Random discrete structures appear as fundamental objects of study in many scientific and mathematical fields including statistical physics, combinatorics, algorithms and complexity, social ch...

We revisit the work of Bourgain, Kahn, Kalai, Katznelson and Linial (1992) -- referred to as ``BKKKL'' in the title -- about influences on Boolean functions in order to give a precise statement of threshold phenomenon on the product space $\{1,..., r\}^\NN$, generalizing one of the main results of a paper by Talagrand (1994).

The classical sharp threshold theorem of Friedgut and Kalai (1996) asserts that any symmetric monotone function $f:\{0,1\}^{n}\to\{0,1\}$ exhibits a sharp threshold phenomenon. This means that the expectation of $f$ with respect to the biased measure $\mu_{p}$ increases rapidly from 0 to 1 as $p$ increases. In this paper we present `robust' versions of the theorem, which assert that it holds also if the function is `almost' monotone, and admits a much weaker notion of symme...

An integer polynomial $p$ of $n$ variables is called a \emph{threshold gate} for a Boolean function $f$ of $n$ variables if for all $x \in \zoon$ $f(x)=1$ if and only if $p(x)\geq 0$. The \emph{weight} of a threshold gate is the sum of its absolute values. In this paper we study how large a weight might be needed if we fix some function and some threshold degree. We prove $2^{\Omega(2^{2n/5})}$ lower bound on this value. The best previous bound was $2^{\Omega(2^{n/8})}$ (Po...

We show that sharp thresholds for Boolean functions directly imply average-case circuit lower bounds. More formally we show that any Boolean function exhibiting a sharp enough threshold at \emph{arbitrary} critical density cannot be computed by Boolean circuits of bounded depth and polynomial size. Our general result implies new average-case bounded depth circuit lower bounds in a variety of settings. (a) ($k$-cliques) For $k=\Theta(n)$, we prove that any circuit of depth...

Gunby-He-Narayanan showed that the logarithmic gap predictions of Kahn-Kalai and Talagrand (proved by Park-Pham and Frankston-Kahn-Narayanan-Park) about thresholds of up-sets do not apply to down-sets. In particular, for the down-set of triangle-free graphs, they showed that there is a polynomial gap between the threshold and the factional expectation threshold. In this short note we give a simpler proof of this result, and extend the polynomial threshold gap to down-sets of ...