2026-07-24T12:23:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11715 2024-03-06T10:48:31Z ddc:004 open_access

On Oblivious Amplification of Coin-Tossing Protocols Bitansky, Nir Geier, Nathan Coin Tossing Amplification Lower Bound Santha Vazirani We consider the problem of amplifying two-party coin-tossing protocols: given a protocol where it is possible to bias the common output by at most ρ, we aim to obtain a new protocol where the output can be biased by at most ρ* < ρ. We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every ρ* < ρ. Such amplifiers ignore the way that the underlying ρ-bias protocol works and can only invoke an oracle that provides ρ-bias bits. We provide two proofs of this impossibility. The first is by a reduction to the impossibility of deterministic randomness extraction from Santha-Vazirani sources. The second is a direct proof that is more general and also rules outs certain types of asymmetric amplification. In addition, it gives yet another proof for the Santha-Vazirani impossibility. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nir Bitansky and Nathan Geier 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.30 urn:nbn:de:0030-drops-117150 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30 eng https://creativecommons.org/licenses/by/3.0/legalcode