Data Structures and Algorithms · arXiv:2611.17223 v1 · submitted 12 Nov 2026 · 24 references
Combinatorial Bernoulli Factories with Polynomially Many Coins
The paper says
“We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases x into a random vertex of a polytope P whose mean is exactly x.”
more of the abstract
For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior x are polynomial in the dimension and in 1/δ*, where δ* = mini{xi,1−xi} is never supplied to the algorithm. For perfect matchings this gives O(n8δ*−2log(n/δ*)) flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least n2n−1 flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside P and the promise that x is far from the boundary of P.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
Holds up. Polynomial-time combinatorial Bernoulli factories for all affine slices of the cube, with a clean batch-and-correct technique and a clever random-reserve trick to eliminate the need for a supplied interior radius. This line is wrong
4 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 24 references say.
4 minor objections
The paper says, at Lemma 4.9
Pith says: minor objection 1 of 4
The proof says that the proof of Lemma 3.3 applies verbatim with beta replaced by c/a, but it does not explicitly verify that the anchor-lottery tilt h_i remains in [0,1] (equivalently, that |c barR_i /(a s)| is at most 1). This follows immediately from (23) together with |barR_i| <= s P[R != 0], but one sentence making that step explicit would make the application self-contained.
The paper says, at Theorem 4.3
Pith says: minor objection 2 of 4
The displayed inclusion O(d^{7/2}/(r delta*^2) log(d/(r delta*))) subset of O(d^{7/2}/delta*^3 log(d/delta*)) is not immediate as written; it uses both r >= delta* and log(1/delta*) <= log(d/delta*) for d >= 1 and delta* <= 1. A one-line justification would prevent a reader from misreading this as a purely algorithmic weakening.
show 2 more
The paper says, at Section 4.3, Lemma 4.6
Pith says: minor objection 3 of 4
In the overshoot bound, the step (e delta*/(4 lambda_l))^{h_l} <= (delta*/lambda_l)^2 (e/4)^{h_l} uses h_l >= 2 and delta*/lambda_l <= 1; these conditions hold for the chosen parameters but are not stated at that point in the proof.
The paper says, at Abstract and typesetting
Pith says: minor objection 4 of 4
Several inline formulas are garbled by missing braces (for example, delta*^{-2} appears as delta-2* and n^8 appears as n8 in the abstract and Section 1); these should be fixed in the final version.
What would settle it
Verify that the Lean 4 formalization covers the key steps of Theorem 4.3, particularly the pilot analysis (Lemma 4.6) and the ratio factory (Lemma 4.8). If the formalization is complete, it confirms the correctness of the central argument.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up
- Skeptic agrees
- Editor wrote the verdict above
- Referee minor revision: 4 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
This paper delivers what it promises: the first polynomial-time combinatorial Bernoulli factory for every affine slice of the cube, exponentially improving the prior race-based factory for perfect matchings. The core technique—batch, project, and correct via a lottery over anchors—is genuinely new and well explained. The random-reserve and ratio-factory trick that removes the need for a supplied interior radius on affine slices is clever and correctly analyzed. The proofs are rigorous, the assumptions are clearly stated, and the limitations (boundary non-termination, dependence on δ*, reliance on oracles) are acknowledged upfront. The Lean 4 formalization adds credibility.
The soft spots are real but not load-bearing. The algorithm's expected flip count diverges as δ* → 0, and it does not terminate on the boundary; the authors say this honestly. The dependence on oracles (Mem, Round) is standard for the polytope model and justified by references to Grötschel, Lovász, and Schrijver. The constant K0 in the linear factory is not optimized, but that is a minor issue. The paper does not claim a uniform bound over the polytope; it gives a pointwise bound that depends on the unknown x, which is appropriate.
Who this is for: anyone working on Bernoulli factories, exact sampling, or the interface of randomized algorithms and polytope theory. The paper deserves a serious referee; it is a clear advance over the state of the art. I would cite it and bring it to a reading group.
Recommendation: accept after minor revision. The only thing I would ask for is a brief discussion of whether the dependence on δ* can be improved or is provably necessary (the authors already cite the Keane-O'Brien characterization for the scalar case, but a short remark would help).
The strongest objection
No significant objection identified. The paper is rigorous, the proofs are complete, and the limitations are clearly stated. The central claim (Theorem 4.3) is supported by the analysis. The algorithm's expected flip count depends polynomially on 1/δ*, which is unavoidable for any factory that is correct on the interior and does not know δ* (as argued by the authors via the Keane-O'Brien characterization). The boundary non-termination is acknowledged and is a known trade-off for interior factories. The reliance on oracles (Mem, Round) is standard for the polytope model and is justified by references to Grötschel, Lovász, and Schrijver. The formalization in Lean 4 adds credibility. The paper does not claim a uniform bound over the polytope; it gives a pointwise bound that depends on the unknown x. This is honest and appropriate.
The reader's verdict is ACCEPT with high confidence, and the weakest assumption identified (reliance on oracles, boundary behavior) is exactly what the paper acknowledges. The stress-test pass finds no hidden flaw. The paper is well-structured, the proofs are self-contained (with a self-contained appendix for the linear factory), and the limitations are clearly stated. The central claim is supported by the mathematical analysis. The only potential concern is the dependence on δ*, but this is inherent to the problem (as the authors argue via the Keane-O'Brien characterization) and is not a flaw in the argument. The paper does not claim a uniform bound, and the pointwise bound is correctly derived. The formalization in Lean 4 provides independent support. Therefore, the verdict should remain ACCEPT.
The referee's report
If the result stands, it is a substantial advance for combinatorial Bernoulli factories: it converts the existence-style dichotomy of Niazadeh, Paes Leme, and Schneider into a polynomial-time exact sampling method for every affine slice of the cube, and it gives the first polynomial expected-flip bound for exact sampling of perfect matchings with prescribed marginals. The exactness is maintained exactly rather than approximately, which is what matters for incentive-compatibility-preserving reductions and for exact simulation applications. The proof structure is analytical and self-contained: the batch-and-project identity E[Y] = x holds for every batch size, concentration is used only to certify a linear-factory promise, and the random-reserve/division-factory construction is a genuine methodological contribution. The paper is also honest about its limitations: boundary non-termination, the dependence on 1/delta*, and the fact that it does not control the output distribution beyond its mean are all stated explicitly. The self-contained appendix and the claimed Lean 4 formalization are additional credibility artifacts. I found no load-bearing gap in the derivations.
Pith's reading of the paper (a machine's summary, not the authors')
This paper claims that combinatorial Bernoulli factories—algorithms that turn coins of unknown biases x into a random vertex of a polytope P whose expectation is exactly x—can be made efficient. For every affine slice of the cube, which is the whole class of polytopes that admit any factory at all, one single algorithm works at every interior point with expected coin flips and running time that are polynomial in the dimension and in 1/δ*, the distance of the bias vector to the cube boundary, a quantity the algorithm is never given. For perfect matchings the bound becomes O($n^{8}$ δ*^{-2} log(n/δ*)) expected flips, against a prior factory that spends at least $n^{{2n−1}}$ flips at the uniform doubly stochastic matrix. The same method rounds exactly on any rational polytope when the target point is promised to stay away from the boundary.
What carries the argument. The batch-and-project identity E[Π(Z)] = x, valid for every batch size because affine projection fixes aff(P) pointwise, together with a random reserve α: the projected point Y is expanded away from the reference point u by the factor 1/(1−α) so that mixing with u in proportions 1−α : α reconstructs Y, and on the rare feasibility failure the residual R = Y − u drives a lottery over the 2d anchors u±i = Π(u ± r e_i), tilted by the linear factory that converts a p-coin into a βp-coin exactly. Dividing by the unknown mean reserve a uses a two-coin race in which the first head identifies the source, with the expected reciprocal cost (c+1)/a cancelling against the probability a of entering the correction, so no lower bound on the denominator ever needs to be known.
Core claim. The central claim is that exact sampling can be restored by batching and correcting rather than by approximating first. Flipping each coin m times and projecting the empirical mean Z onto aff(P) yields a point Y with expectation exactly x for every batch size m, because the projection is affine and fixes aff(P) pointwise; this is identity (3). The projection can fall outside P, but under a boundary margin that happens with exponentially small probability, and when it does, the lost residual R = Y − u is restored through a lottery over the 2d anchors u±i = Π(u ± r e_i), feasible points inside the ball of radius r about a reference point u. The lottery tilt is set by an observed residual through a linear Bernoulli factory, so the output mean equals x exactly because the residual is added back rather than discarded. On affine slices of the cube, a pilot stage estimates the scale δ*, but an exact algorithm cannot trust such an estimate, so instead the reserve probability is made random and the correction divides by the unknown mean reserve using a two-coin race, whose expected reciprocal cost cancels against the reserve itself. The concentration bound certifies only that the linear factory is used within its promise; it never enters the computation of the output mean.
The premise it rests on. The load-bearing premise is that the polytope P comes with exact polynomial-time oracles for membership testing and for decomposing a point into vertices, and that the unknown bias vector x lies strictly inside P with no coordinate equal to 0 or 1; on the boundary the algorithm provably stalls and never terminates.
If the paper is right (Pith's inferences, not the authors')
The black-box mechanism-design reduction that motivated combinatorial factories becomes computationally efficient, since a polynomial coin budget means only polynomially many allocation runs per output.
Perfect matchings can be sampled from unknown edge marginals in O(n^8 δ*^{-2} log(n/δ*)) expected flips, an exponential improvement over the n^{2n−1}-flip race of the earlier factory at the uniform matrix.
On matroid base polytopes and nonbipartite perfect-matching polytopes, which are not affine slices and so admit no full-domain factory, the promised-distance version still runs exactly in polynomial time on interior regions.
Exactness is preserved exactly, not approximately: the output vertex's mean equals x, so errors do not compound across iterations of the kind of exact-simulation or mechanism-design pipeline these factories feed.
The pattern of paying for an error with the error's own coin—dividing by an unknown mean reserve whose reciprocal cost cancels—may generalize to other exact sampling problems in which an acceptance probability plays the role of the denominator, removing the need for lower-bound advice more broadly.
Because the guarantee depends on δ* while the algorithm is never told it, the same pilot-plus-random-reserve structure could be reused to estimate other problem-specific margin parameters instead of being handed them.
A testable extension is whether the d^{7/2} dimension exponent and the logarithmic factor can be tightened, or whether a matching lower bound in 1/δ* exists; the authors note they did not try to optimize the polynomial.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases x into a random vertex of a polytope P whose mean is exactly x. For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior x are polynomial in the dimension and in 1/δ*, where δ* = mini{xi,1−xi} is never supplied to the algorithm. For perfect matchings this gives O(n8δ*−2log(n/δ*)) flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least n2n−1 flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside P and the promise that x is far from the boundary of P.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-14
The authors' main claim, as the classifier picked it out 0.60
“For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior $x$ are polynomial in the dimension and in $1/{\delta_*}$, where ${\delta_*}=\min_i\{x_i,1-x_i\}$ is never supplied to the algorithm.”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.85 · human participants 0.02 · controlled comparison 0.38 · randomized assignment 0.03 · states quantitative result 0.98 · compares with prior results 0.98 · mentions code or data availability 0.08
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| We provide an efficient implementation of combinatorial Bernoulli factories. | contribution 1.00 | 0.95 | 0.48 | asserted 1.00 |
| Such a factory turns coins of unknown biases $x$ into a random vertex of a polytope $P$ whose mean is exactly $x$. | background 0.95 | 0.29 | 0.12 | asserted 1.00 |
| For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior $x$ are polynomial in the dimension and in $1/{\delta_*}$, where ${\delta_*}=\min_i\{x_i,1-x_i\}$ is never supplied to the algorithm. | contribution 0.67 | 0.94 | 0.57 | asserted 1.00 |
| For perfect matchings this gives $O(n^{8}{\delta_*}^{-2}\log(n/{\delta_*}))$ flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least $n^{2n-1}$ flips in expectation at the uniform doubly stochastic matrix. | result 0.98 | 0.81 | 0.20 | asserted 1.00 |
| For other polytopes, our method rounds exactly given a point deep inside $P$ and the promise that $x$ is far from the boundary of $P$. | limitation 0.78 | 0.88 | 0.10 | asserted 0.99 |
What kind of paper the classifier reports this is: method or tool 0.98 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-14: 1 request, 4,504 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Figures (2)
Figures are the authors', reproduced from the paper.
References (24)
- [1] A. Beskos and G. O. Roberts. Exact simulation of diffusions.Annals of Applied Probability, 15(4):2422– 2444, 2005 on Pith
- [2] Y. Cai, A. Oikonomou, G. Velegkas, and M. Zhao. An efficientε-BIC to BIC transformation and its application to black-box reduction in revenue maximization. InProc. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021 on Pith
- [3] H. Dale, D. Jennings, and T. Rudolph. Provable quantum advantage in randomness processing.Nature Communications, 6:8203, 2015 on Pith
- [4] S. Dughmi, J. D. Hartline, R. D. Kleinberg, and R. Niazadeh. Bernoulli factories and black-box reductions in mechanism design.Journal of the ACM, 68(2), Article 10, 2021. Preliminary version in STOC2017 on Pith
- [5] J. M. Flegal and R. Herbei. Exact sampling for intractable probability distributions via a Bernoulli factory.Electronic Journal of Statistics, 6:10–37, 2012 on Pith
- [6] M. Grötschel, L. Lovász, and A. Schrijver.Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics 2. Springer, 1988 on Pith
- [7] F. B. Gonçalves, K. Łatuszyński, and G. O. Roberts. Barker’s algorithm for Bayesian inference with intractable likelihoods.Brazilian Journal of Probability and Statistics, 31(4):732–745, 2017 on Pith
- [8] F. B. Gonçalves, K. Łatuszyński, and G. O. Roberts. Exact Monte Carlo likelihood-based inference for jump-diffusion processes.Journal of the Royal Statistical Society Series B, 85(3):732–756, 2023 on Pith
- [9] W. Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58(301):13–30, 1963 on Pith
- [10] M. Huber. Nearly optimal Bernoulli factories for linear functions.Combinatorics, Probability and Computing, 25(4):577–591, 2016 on Pith
- [11] M. Huber. Optimal linear Bernoulli factories for small mean problems.Methodology and Computing in Applied Probability, 19(2):631–645, 2017 on Pith
- [12] M. S. Keane and G. L. O’Brien. A Bernoulli factory.ACM Transactions on Modeling and Computer Simulation, 4(2):213–219, 1994 on Pith
- [13] J. Koskela, T. Karvonen, K. Łatuszyński, and D. Spanò. A debiased Bernoulli factory and unbiased estimation of a probability. arXiv:2510.01941, 2025 on PithPith's reviewarXiv
- [14] K. Łatuszyński, I. Kosmidis, O. Papaspiliopoulos, and G. O. Roberts. Simulating events of unknown probabilities via reverse time martingales.Random Structures & Algorithms, 38(4):441–452, 2011 on Pith
- [15] L. Mendo. An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series.Stochastic Processes and their Applications, 129(11):4366–4384, 2019. 19 on Pith
- [16] G. Morina.Extending the Bernoulli Factory to a Dice Enterprise. PhD thesis, University of Warwick, 2021 on Pith
- [17] G. Morina, K. Łatuszyński, P. Nayar, and A. Wendland. From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains.Annals of Applied Probability, 32(1):327–359, 2022 on Pith
- [18] E. Mossel and Y. Peres. New coins from old: computing with unknown bias.Combinatorica, 25(6):707– 724, 2005 on Pith
- [19] Ş. Nacu and Y. Peres. Fast simulation of new coins from old.Annals of Applied Probability, 15(1A):93–115, 2005 on Pith
- [20] R. Niazadeh, R. Paes Leme, and J. Schneider. Combinatorial Bernoulli factories.Bernoulli, 29(2):1246– 1274, 2023. Preliminary version inSTOC2021 on Pith
show 4 more
- [21] R. Niazadeh, R. Paes Leme, and J. Schneider. Bernoulli factories for flow-based polytopes.SIAM Journal on Discrete Mathematics, 38(1), 2024 on Pith
- [22] R. Paes Leme and J. Schneider. Multiparameter Bernoulli factories.Annals of Applied Probability, 33(5):3987–4007, 2023 on Pith
- [23] M. R. Sampford. On sampling without replacement with unequal probabilities of selection.Biometrika, 54(3–4):499–513, 1967 on Pith
- [24] J. von Neumann. Various techniques used in connection with random digits.National Bureau of Standards Applied Mathematics Series, 12:36–38, 1951. A A self-contained linear factory For completeness, we give a non-optimized exponent-process implementation of the scalar primitive... on Pith
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment