  In his seminal work, Cleve [STOC '86] has proved that any $r$-round
coin-flipping protocol can be efficiently biased by $\Theta(1/r)$. This lower
bound was met for the two-party case by Moran, Naor, and Segev [Journal of
Cryptology '16], and the three-party case (up to a $polylog$ factor) by Haitner
and Tsfadi [SICOMP '17], and was approached for $n$-party protocols when $n<
loglog r$ by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For $n> loglog
r$, however, the best bias for $n$-party coin-flipping protocols remains
$O(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch, Blum, Chor,
Goldwasser, and Micali [Manuscript '85].
  Our main result is a tighter lower bound on the bias of coin-flipping
protocols, showing that, for every constant $\epsilon >0$, an
$r^{\epsilon}$-party $r$-round coin-flipping protocol can be efficiently biased
by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first
improvement of Cleve's bound, and is only $n=r^{\epsilon}$ (multiplicative) far
from the aforementioned upper bound of Awerbuch et al.
