Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis +1

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…