Combinatorial Bernoulli Factories with Polynomially Many Coins
Combinatorial Bernoulli factories turn coins of unknown biases x into a random vertex of a polytope P whose mean is exactly x. The prior factory of Niazadeh, Paes Leme, and Schneider is very slow: on the Birkhoff polytope it uses at least n^{2n-1} flips in expectation.
Flip every coin in batches, take the empirical mean, and project it orthogonally onto the affine hull of P, which preserves unbiasedness exactly. If the projected point is feasible, round it to a vertex. If it is infeasible (a rare event), round a known interior point instead and keep the residual rather than discarding the sample. For affine slices of the cube, a pilot estimate of the margin δ* = min_i{x_i, 1-x_i} replaces any supplied promise. The results were formalized in Lean 4.
For every affine slice of the cube, a single algorithm is given whose expected coin flips and running time are polynomial in the dimension and 1/δ*, without δ* being supplied. For perfect matchings this gives O(n^8 δ*^{-2} log(n/δ*)) flips. For general polytopes, exact rounding is achieved given a point deep inside P and a promised margin for x.
