{"id":"f284b001-e4cb-47f8-9258-2e0881550c2b","arxiv_id":"2611.17223","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"partial","parameter_count":1,"one_line_summary":"A polynomial-time combinatorial Bernoulli factory for every affine slice of the cube, with expected coin flips polynomial in dimension and 1/δ* (the minimum distance to the cube boundary), without knowing δ*.","lead":"This paper gives a new algorithm for combinatorial Bernoulli factories that turns coins of unknown biases into random vertices of a polytope with exact mean. The algorithm runs in polynomial time and uses polynomially many coin flips, exponentially improving over prior work for perfect matchings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"The algorithm's dependence on δ* in the universal setting is not uniform: the expected flip bound diverges as δ* → 0, and the algorithm does not terminate on the boundary. This is an acknowledged limitation, not a flaw in the proof.","rationale":"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.","tokens_in":22695,"tokens_out":504,"duration_ms":202149,"concrete_test":"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.","verdict_should_be":"UNCHANGED","load_bearing_attack":"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.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper gives efficient combinatorial Bernoulli factories: algorithms that, given reusable coins of unknown biases x inside a polytope P, output a random vertex V with E[V] = x exactly. The first main result (Theorem 3.1) is an 'Interior' algorithm for any rational polytope supplied with a rational interior point u and a promise that the unknown x lies in the rho-interior of P; it uses batch-and-project, a random reserve, and a correction lottery over anchored feasible points, with expected flips polynomial in d, 1/r, and 1/rho. The second and central result (Theorem 4.3) removes the supplied rho for affine slices of the cube: a pilot estimates the scale delta* = min_i{x_i, 1-x_i} without ever being told delta*, a random reserve replaces the fixed reserve, and a ratio factory divides by the unknown mean reserve, so the 1/a cost of the division cancels against the probability a of entering the correction. This yields a single algorithm correct at every interior point of every affine slice, with expected flips O(d^{7/2}/delta*^3 log(d/delta*)). Corollary 4.4 specializes to perfect matchings with O(n^8 delta*^{-2} log(n/delta*)) flips, versus the exponential n^{2n-1} expected flips of the previous race-based factory at the uniform doubly stochastic matrix. Appendix A supplies a self-contained linear factory. The paper explicitly acknowledges that the universal factory does not terminate on the boundary and that the flip bound is not uniform near the boundary.","tokens_in":24154,"tokens_out":1212,"duration_ms":182317,"significance":"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Lemma 4.9","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Theorem 4.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 4.3, Lemma 4.6","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Abstract and typesetting","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"minor_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"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.\n\nThe 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.\n\nWho 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.\n\nRecommendation: 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).","headline":"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.","tokens_in":23449,"tokens_out":464,"duration_ms":9916},"pith_extraction":{"msc":["60C05","68W20"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"For every affine slice of the cube—the entire class of polytopes admitting a Bernoulli factory—a single batch-and-correct algorithm now samples exactly at every interior point using O(d^{7/2} δ*^{-3} log(d/δ*)) expected coin flips, where…","keywords":["Bernoulli factory","combinatorial sampling","exact sampling","affine slice of the cube","perfect matchings","Birkhoff polytope","polytope rounding","unbiased estimation"],"falsifier":"Run the Universal algorithm on the Birkhoff polytope at the uniform matrix U for a few small n and record the expected number of input-coin flips: if it is not within the claimed O($n^{8}$ δ*^{-2} log(n/δ*)) bound with δ* = 1/n, roughly $n^{{10}}$ log n flips, but instead grows exponentially, the cost theorem fails. Conversely, to probe the boundary limitation, set one entry of the matrix to 0 and check whether the pilot stage stalls as the paper says, never collecting its required heads or tails.","tokens_in":24141,"feed_emoji":"🎲","tokens_out":5781,"duration_ms":35659,"temperature":0.7,"pith_summary":"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.","feed_headline":"Bernoulli factory for matchings cut to n^8 coin flips","feed_subtitle":"One batch-and-correct algorithm covers every affine-slice polytope exactly, in time polynomial in dimension and 1/δ*, with the margin…","key_machinery":"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_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the polytope formulation, the characterization (1) that affine slices are exactly the factory-admissible polytopes, and the n^{2n−1}-flip race at the uniform matrix that the new bound must beat.","marker":"[20]"},{"why":"Provides the linear Bernoulli factory p ↦ βp, the exact primitive used to tilt the anchor lottery.","marker":"[10]"},{"why":"Supplies the two-coin algorithm used to divide by the unknown mean reserve a without a lower bound on it.","marker":"[7]"},{"why":"Supplies the constructive Carathéodory vertex-decomposition that realizes the Round oracle for explicitly given polytopes.","marker":"[6]"},{"why":"Gives the Hoeffding concentration used to certify that the feasibility-failure correction is rarely needed.","marker":"[9]"},{"why":"Provides the view of a factory as debiasing a biased estimator, the conceptual template the batch-and-correct construction follows.","marker":"[16]"}],"fun_headline_variants":[],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":[]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":8.1e-05,"raw_usage":{"cost":8.08262e-05,"is_byok":false,"cost_details":{"upstream_inference_cost":8.08262e-05,"upstream_inference_prompt_cost":8.04622e-05,"upstream_inference_completions_cost":3.64e-07},"total_tokens":1091,"prompt_tokens":1089,"completion_tokens":2,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":1089,"tokens_out":2,"cost_source":"openrouter_usage","duration_ms":2311,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T09:01:01.795248+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"Run the Universal algorithm on the Birkhoff polytope at the uniform matrix U for a few small n and record the expected number of input-coin flips: if it is not within the claimed O($n^{8}$ δ*^{-2} log(n/δ*)) bound with δ* = 1/n, roughly $n^{{10}}$ log n flips, but instead grows exponentially, the cost theorem fails. Conversely, to probe the boundary limitation, set one entry of the matrix to 0 and check whether the pilot stage stalls as the paper says, never collecting its required heads or tails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the polytope formulation, the characterization (1) that affine slices are exactly the factory-admissible polytopes, and the n^{2n−1}-flip race at the uniform matrix that the new bound must beat."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the linear Bernoulli factory p ↦ βp, the exact primitive used to tilt the anchor lottery."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the two-coin algorithm used to divide by the unknown mean reserve a without a lower bound on it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the constructive Carathéodory vertex-decomposition that realizes the Round oracle for explicitly given polytopes."},{"cited_title":"Hoeffding","cited_arxiv_id":null,"evidence_quote":"Gives the Hoeffding concentration used to certify that the feasibility-failure correction is rarely needed."},{"cited_title":"Morina.Extending the Bernoulli Factory to a Dice Enterprise","cited_arxiv_id":null,"evidence_quote":"Provides the view of a factory as debiasing a biased estimator, the conceptual template the batch-and-correct construction follows."}],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}