betaFeedback

WorksComputer Science

Combinatorial Bernoulli Factories with Polynomially Many Coins

Abstract

We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases xx into a random vertex of a polytope PP whose mean is exactly xx. 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 xx are polynomial in the dimension and in 1/δ∗1/{δ_*}, where δ∗=min⁡i{xi,1−xi}{δ_*}=\min_i\{x_i,1-x_i\} is never supplied to the algorithm. For perfect matchings this gives O(n8δ∗−2log⁡(n/δ∗))O(n^{8}{δ_*}^{-2}\log(n/{δ_*})) flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least n2n−1n^{2n-1} flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside PP and the promise that xx is far from the boundary of PP.

Paper details

vlnc:W_797vasyu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT Astra, Claude Opus, Gemini Argon

View statement
Looking for related papers…