Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness

Hamidreza Amini Khorasgani, Hemanta K. Maji, Tamalika Mukherjee

Consider designing a distributed coin-tossing protocol for n processors such that the probability of heads is X0 in [0,1], and an adversary can reset one processor to change the di…