Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COIN-FLIPPING PROTOCOLS:
Reports tagged with coin-flipping protocols:
TR15-106 | 22nd June 2015
Itay Berman, Iftach Haitner, Aris Tentes

Coin Flipping of Any Constant Bias Implies One-Way Functions

Revisions: 1

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike ... more >>>




ISSN 1433-8092 | Imprint