Asymptotically Optimal Gap Finders for Boolean-Terminal Martingales

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

A martingale that starts at \(\mu\) and ends in \(\{0,1\}\) has to jump somewhere, and an attack on a coin-flipping protocol is a rule for catching a jump as it happens. The classical bound catches a jump of size \(\Omega(\mu/\sqrt{n})\) with probability \(\Omega(\mu)\) — a product with two factors of \(\mu\) in it, which is harmless when \(\mu\) is a constant and lossy when it is not. The conjecture is that one factor is an artifact.

View PDF · Download LaTeX source

For a martingale \(\mathbf{w}_{\le n}\) and an online stopping algorithm \(\mathsf{Stop}\) with stopping time \(\tau\), call \(\mathsf{Stop}\) a \((\rho, \alpha)\) gap finder if \[\rho = \Pr\left[\left|w_{\tau} - w_{\tau-1}\right| \ge \alpha\right],\] the probability over the martingale and \(\mathsf{Stop}\)’s coins. Online means the rule sees \(w_1, \ldots, w_i\) and decides whether to stop, with no lookahead.

Conjecture. There is a universal constant \(c > 0\) — independent of \(n\), of \(\mu\), and of the martingale — such that for every \(n\), every \(\mu \in (0, 1/2]\), and every martingale \(\mathbf{w}_{\le n}\) with \(\mathbb{E}[\mathbf{w}_1] = \mu\) and \(\Pr[\mathbf{w}_n \in \{0,1\}] = 1\), extended by \(\mathbf{w}_0 := \mu\) and \(\mathbf{w}_{n+1} := \mathbf{w}_n\), there exist a real \(\alpha > 0\) and an online stopping algorithm \(\mathsf{Stop}\) that is a \((\rho, \alpha)\) gap finder with \[\rho \cdot \alpha \ \ge\ \frac{c\,\mu}{\sqrt{n}}.\]

No bound is placed on the running time of \(\mathsf{Stop}\): the statement is information-theoretic. That the constant must be independent of \(\mu\) is the whole point — it is exactly the paper’s complaint about the existing bound.

Open for small \(\mu\), and the gap between what is known and what is asked is a single factor of \(\mu\).

What is known. Cleve and Impagliazzo give a gap finder with \(\rho = \Omega(\mu)\) and \(\alpha = \Omega(\mu/\sqrt{n})\), hence \(\rho\alpha = \Omega(\mu^{2}/\sqrt{n})\). Their theorem was proved for \(\mu = 1/2\); the same argument yields the \(\mu\)-dependent bound, and it is that dependence which degrades.

Where it is already enough. For \(\mu = \Theta(1)\) the two bounds coincide up to constants, so the conjecture is settled in that regime; the content is entirely in small \(\mu\).

A neighbouring result that does not settle it. Khorasgani, Maji and Mukherjee prove a different guarantee — an expected gap of \(2\mu(1-\mu)/\sqrt{2n-1}\) — with no probability parameter attached. A gap finder has to name both how often it stops on a jump and how big that jump is, so an expectation bound is not directly comparable, and the source paper says it does not know how to convert it.

Gap finders matter because they convert into attacks: a rule that catches a large jump with decent probability is a strategy for a corrupted party to bias the outcome. The small-\(\mu\) regime is the one that matters for strongly biased protocols, where the honest outcome is already rare and an attacker is trying to make it rarer.

A note on how much weight to put on this. The appendix that poses the question describes itself as included “merely for sake of completeness”, and its observations are subsumed by the paper’s main theorem; the recursive composition it promises is, by the paper’s own remark, super-polynomial for \(k = \omega(1)\) corruptions. So this is a clean open question about martingales rather than the missing piece of the paper’s headline result, and it is worth stating plainly which of the two it is.

Prove or refute the \(\Omega(\mu/\sqrt{n})\) product bound for general \(\mu \in (0, 1/2]\), with a \(\mu\)-independent constant.
Determine whether an expected-gap guarantee can be converted into a \((\rho, \alpha)\) gap finder, which the source says it does not know how to do.
Settle whether the conjectured bound is itself optimal, or whether the truth is larger still for small \(\mu\).
Work out what the improvement would actually buy for coin-tossing attacks, given that the recursive composition is super-polynomial beyond constantly many corruptions.
Formalize the statement in Lean. Martingales with Boolean terminal value and online stopping rules need writing first.

Etesami, Gao, Mahloujifar, and Mahmoody. Polynomial-time targeted attacks on coin tossing for any number of corruptions. Cryptology ePrint Archive, Report 2021/1464; TCC 2021. Appendix C, where the question is posed and declared open, and Remark 46 on the cost of the recursive composition.
Cleve and Impagliazzo. Martingales, collective coin flipping and discrete control processes. Unpublished manuscript, 1993. The gap finder the conjecture asks to improve; cited as the manuscript it is.
Khorasgani, Maji, and Mukherjee. Estimating gaps in martingales and applications to coin-tossing: constructions and hardness. TCC 2019, pp. 333–355. The expected-gap guarantee that does not directly compare.
Ben-Or and Linial. Collective coin flipping, robust voting schemes and minima of Banzhaf values. FOCS 1985, pp. 408–416. Where collective coin flipping is introduced.