Pith.

Data Structures and Algorithms · arXiv:2611.17223 v1 · submitted 12 Nov 2026 · 24 references

Combinatorial Bernoulli Factories with Polynomially Many Coins

Renato Paes Leme, Rad Niazadeh

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

Are you an author? What you can do.

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

  1. Reader holds up confidence high
  2. Skeptic agrees 3 min 22 s · 22,695 tokens read, 504 written
  3. Editor wrote the verdict above 10 s · 23,449 tokens read, 464 written
  4. Referee minor revision: 4 minor 3 min 2 s · 24,154 tokens read, 1,212 written

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

Every value above, in the review's public record (JSON)

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.

Request a human review

How Pith checks papers · The full audit of this paper

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.

SentenceRoleThe authors' own workStates the main conclusionStrength
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)
Figure 1 of the paper
Figure 1. The batch, drawn for d = 2 with aff(P) a line. The empirical mean Z of m rounds of flips need not lie on aff(P); its projection Y = Π(Z) does, and E Y = x exactly. The ball B(x, ρ) ∩ aff(P) lies in P and Z concentrates around x, so Y is feasible except on a rare event, as for Z ′ ; the algorithm then rounds u instead, and keeps the residual Y ′ − u rather than discarding the sample. 3.1 Batch and project The natural first attempt is to estimate x and round the estimate. Flip every coin m times: the t-th round of flips is a vector Xt ∈ {0, 1} d with E Xt = x, and the empirical mean Z…
Figure 2 of the paper
Figure 2. The anchors, drawn for dim aff(P) = 2. The ball B(u, r) ∩ aff(P) lies in P, so the 2d points u ± i = Π(u ± rei) are feasible. The correction picks i uniformly, chooses between u + i and u − i with a coin tilted by the observed residual, and decomposes the chosen point into vertices; the resulting vertex lottery has mean exactly u + R/α ¯ , a point inside the ball that the algorithm never computes. Taking 2hi − 1 = d rαR¯ i makes this u + 1 αΠLR¯ = u + R/α ¯ , because R¯ ∈ L is fixed by ΠL. So this lottery reaches the target (6), and since it is a lottery over points of P, the…

Figures are the authors', reproduced from the paper.

References (24)
  1. [1] A. Beskos and G. O. Roberts. Exact simulation of diffusions.Annals of Applied Probability, 15(4):2422– 2444, 2005 on Pith
  2. [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. [3] H. Dale, D. Jennings, and T. Rudolph. Provable quantum advantage in randomness processing.Nature Communications, 6:8203, 2015 on Pith
  4. [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. [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. [6] M. Grötschel, L. Lovász, and A. Schrijver.Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics 2. Springer, 1988 on Pith
  7. [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. [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. [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. [10] M. Huber. Nearly optimal Bernoulli factories for linear functions.Combinatorics, Probability and Computing, 25(4):577–591, 2016 on Pith
  11. [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. [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. [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. [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. [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. [16] G. Morina.Extending the Bernoulli Factory to a Dice Enterprise. PhD thesis, University of Warwick, 2021 on Pith
  17. [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. [18] E. Mossel and Y. Peres. New coins from old: computing with unknown bias.Combinatorica, 25(6):707– 724, 2005 on Pith
  19. [19] Ş. Nacu and Y. Peres. Fast simulation of new coins from old.Annals of Applied Probability, 15(1A):93–115, 2005 on Pith
  20. [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
  1. [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
  2. [22] R. Paes Leme and J. Schneider. Multiparameter Bernoulli factories.Annals of Applied Probability, 33(5):3987–4007, 2023 on Pith
  3. [23] M. R. Sampford. On sampling without replacement with unequal probabilities of selection.Biometrika, 54(3–4):499–513, 1967 on Pith
  4. [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.

No comments yet.

Sign in to comment