  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 $d$
deciding the presence of a size $k$ clique in a random graph requires
exponential-in-$n^{\Theta(1/d)}$ size. To the best of our knowledge, this is
the first average-case exponential size lower bound for bounded depth (not
necessarily monotone) circuits solving the fundamental $k$-clique problem (for
any $k=k_n$).
  (b)(random 2-SAT) We prove that any circuit of depth $d$ deciding the
satisfiability of a random 2-SAT formula requires
exponential-in-$n^{\Theta(1/d)}$ size. To the best of our knowledge, this is
the first bounded depth circuit lower bound for random $k$-SAT for any value of
$k \geq 2.$ Our results also provide the first rigorous lower bound in
agreement with a conjectured, but debated, ``computational hardness'' of random
$k$-SAT around its satisfiability threshold.
  (c)(Statistical estimation -- planted $k$-clique) Over the recent years,
multiple statistical estimation problems have also been proven to exhibit a
``statistical'' sharp threshold, called the All-or-Nothing (AoN) phenomenon. We
show that AoN also implies circuit lower bounds for statistical problems. As a
simple corollary of that, we prove that any circuit of depth $d$ that solves to
information-theoretic optimality a ``dense'' variant of the celebrated planted
$k$-clique problem requires exponential-in-$n^{\Theta(1/d)}$ size.
