論文の概要: Combinatorial Bernoulli Factories with Polynomially Many Coins
- arxiv url: http://arxiv.org/abs/2611.17223v1
- Date: Thu, 12 Nov 2026 18:19:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.583556
- Title: Combinatorial Bernoulli Factories with Polynomially Many Coins
- Title(参考訳): ポリノミカルな多面体を有する組合せベルヌーイ因子
- Abstract要約: そのような工場は、未知のバイアスのコインを、正確に$x$であるポリトープ$P$のランダムなランダムに変換する。
他のポリトープの場合、我々のメソッドラウンドは$P$の奥深くにあるポイントを正確に与え、$x$は$P$の境界から遠く離れていると約束する。
- 参考スコア(独自算出の注目度): 5.8941477980664585
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 ${δ_*}=\min_i\{x_i,1-x_i\}$ is never supplied to the algorithm. For perfect matchings this gives $O(n^{8}{δ_*}^{-2}\log(n/{δ_*}))$ 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. 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$.
- Abstract(参考訳): 我々は、組合せベルヌーイ工場の効率的な実装を提供する。
そのような工場は、未知のバイアスのコインを、正確には$x$であるポリトープ$P$のランダム頂点に変換する。
立方体のすべてのアフィンスライス(ファクトリーを許容するポリトープのクラス)に対して、1つのアルゴリズムを与え、その1/{δ_*}$において、1/{δ_*} =min_i\{x_i,1-x_i\}$はアルゴリズムに供給されない。
完全マッチングに対しては、$O(n^{8}{δ_*}^{-2}\log(n/{δ_*})$ flips を与えるが、Niazadeh, Paes Leme, and Schneider [STOC 2021] のファクトリーは、一様の確率行列に対する期待に少なくとも$n^{2n-1}$ flips を使う。
他のポリトープの場合、我々のメソッドラウンドは$P$の奥深くにあるポイントを正確に与え、$x$は$P$の境界から遠く離れていると約束する。
関連論文リスト
- Explicit reduced APN permutations: ramification and optimal Galois-ring lifts [0.0]
3le rm$と$gcd(r,m)=1$を持つ任意の奇数$に対して、削減された$P_m,r=mathrmred(T_r3)2m-2を与える。
最適なAPN置換 $p$ of $mathbbF_q$, every $kge2$, every lift $F$ of $p$ to $mathrmGR (2k,m)$ は単項ではない。
論文 参考訳(メタデータ) (2026-10-15T03:34:29Z) - Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits [0.17398560678845074]
我々は、$|langle x|U|0nrangle|2$ to additive error $varepsilon$ in $mathrmpoly(n, 1/varepsilon)$ timeを推定する決定論的古典的アルゴリズムを与える。
論文 参考訳(メタデータ) (2026-10-01T17:49:01Z) - Efficiently Batching Unambiguous Interactive Proofs [8.993111413196559]
例えば、$Lotimes k$に属するステートメントのセット$k$-tuplesは、複雑さを伴うあいまいなインタラクティブな証明を持つ。 $ellcdotmathsfpolylog(k)$、$acdot ellcdotmathsfpolylog(k)$、ラウンドごとの通信である。
論文 参考訳(メタデータ) (2025-10-21T21:04:10Z) - Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳(メタデータ) (2025-02-25T19:08:26Z) - Efficient approximate unitary designs from random Pauli rotations [3.29295880899738]
単純リー群上のランダムウォークを構築して、任意のモーメントから$t$までのすべてのモーメントに対してすぐにハール測度に収束する。
具体的には、次元 2mathsf n$ のユニタリ群または直交群上のウォークのステップは、ランダムなパウリ回転 $emathrm i theta P /2$ である。
我々の単純な証明はリー代数の二次カシミール作用素を用いる。
論文 参考訳(メタデータ) (2024-02-07T20:34:36Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文 参考訳(メタデータ) (2020-08-20T01:04:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。