#### Milestone Year

### 1998

#### Sharp thresholds and the k-SAT problem

Threshold phenomena are abundant in physics, mathematics,
and computer science. A typical example is water freezing
almost instantaneously as its temperature drops below zero.
At first encounter it is slightly surprising that such behavior
is observed in almost any random mathematical object
where the behavior depends (continuously) on a parameter
that governs this random behavior.
Examples include the emergence of the giant component in random graphs
(first observed by Erdos and Renyi in 1959-60),
the critical rate for Galton-Watson processes,
or the threshold for the existence of a unique Gibbs measure.

A famous example where such behavior was conjectured,
and strongly suggested by simulations,
but evaded formal proof was the satisfiability of a random k-CNF formula
("The k-SAT problem").

In 1998, Weizmann scientists managed to give a very general characterization
of random structures for which sharp threshold behavior must exist.
Applying this criterion to the k-SAT problem,
established the existence of a sharp threshold for this problem.