Gap finders for Boolean-terminal martingales

Coin-flipping attacks reduce to one question: how large a jump can an online stopping rule catch, and how often?

Motivation

Collective coin flipping asks how far an adversary controlling a few of \(n\) parties can push the output of a protocol in which each party broadcasts one message. The standard handle is the Doob martingale of the output bit: with \(b = f(w_1, \ldots, w_n)\) the Boolean output and \(\mathbf{w}_i\) the conditional probability that \(b = 1\) given the first \(i\) messages, the sequence \((\mathbf{w}_1, \ldots, \mathbf{w}_n)\) starts at \(\mu = \Pr[b=1]\) and ends in \(\{0,1\}\).

Such a martingale must jump somewhere, and an attack is exactly a rule for catching a jump online — a gap finder. Cleve and Impagliazzo showed one exists that, with probability \(\Omega(\mu)\), stops at a step whose increment has magnitude \(\Omega(\mu/\sqrt{n})\), giving the product \(\rho\alpha = \Omega(\mu^{2}/\sqrt{n})\). Their argument was written for \(\mu = 1/2\), where the two \(\mu\) factors are constants and nothing is lost.

For small \(\mu\) they are not constants, and the bound degrades by a factor \(\mu\) relative to what one would want. Whether that loss is real is the question here: the conjecture is that a gap finder achieving \(\rho\alpha = \Omega(\mu/\sqrt{n})\) exists for every \(\mu\), with a constant that does not depend on \(\mu\).

Provenance and history

One source paper: Etesami, Gao, Mahloujifar and Mahmoody, Polynomial-time targeted attacks on coin tossing for any number of corruptions, ePrint 2021/1464; TCC 2021. Verified against ePrint on 18 August 2026.

The question is posed in that paper’s Appendix C, in its own voice — “which as far as we know is open” — and stays open through the end of the appendix. The statement was drafted by scripts/harvest_conjectures.py and is AI-written and unreviewed, as its status badge says.

One framing point the draft’s provenance file raised is worth carrying here: the appendix that poses the question is described by the paper itself as included “merely for sake of completeness” and as subsumed by its main theorem. The question is genuinely open, but it is not the paper’s headline, and a page that presented it as the missing piece of the paper’s main result would be overselling it.

Parameter lattice

One axis — the martingale’s starting value \(\mu\) — and the known bounds on the product \(\rho\alpha\) a gap finder can guarantee.

regime best known conjectured status
\(\mu = \Theta(1)\) \(\Omega(\mu^2/\sqrt{n}) = \Omega(\mu/\sqrt{n})\) same settled — the two agree when \(\mu\) is bounded away from \(0\)
\(\mu \le 1/2\) general \(\Omega(\mu^{2}/\sqrt{n})\) \(\Omega(\mu/\sqrt{n})\) open — c/0030

A separate line gives an expected gap of \(2\mu(1-\mu)/\sqrt{2n-1}\) with no accompanying probability parameter, which is not directly comparable: a gap finder must name both how often it stops on a jump and how large that jump is.

Statements in this hub