論文の概要: An efficient construction of Raz's two-source randomness extractor with improved parameters
- arxiv url: http://arxiv.org/abs/2506.15547v1
- Date: Wed, 18 Jun 2025 15:18:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-19 19:35:51.711594
- Title: An efficient construction of Raz's two-source randomness extractor with improved parameters
- Title（参考訳）: 改良されたパラメータをもつRazの2ソースランダム性抽出器の効率的な構成
- Authors: Cameron Foreman, Lewis Wooltorton, Kevin Milner, Florian J. Curchod,
- Abstract要約: 2ソースランダムネス抽出器は弱いランダムソースをほぼ完全なランダム数に蒸留する。
ラズの抽出器は、1つの源がその長さに比例する線形のミンエントロピーを持つような環境でこれを初めて達成した。
本稿では、準線形計算時間を持つRazの抽出器の改良版と、エントロピー要求を低減した新しい解析定理を提案する。
- 参考スコア（独自算出の注目度）: 0.14999444543328289
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Randomness extractors are algorithms that distill weak random sources into near-perfect random numbers. Two-source extractors enable this distillation process by combining two independent weak random sources. Raz's extractor (STOC '05) was the first to achieve this in a setting where one source has linear min-entropy (i.e., proportional to its length), while the other has only logarithmic min-entropy in its length. However, Raz's original construction is impractical due to a polynomial computation time of at least degree 4. Our work solves this problem by presenting an improved version of Raz's extractor with quasi-linear computation time, as well as a new analytic theorem with reduced entropy requirements. We provide comprehensive analytical and numerical comparisons of our construction with others in the literature, and we derive strong and quantum-proof versions of our efficient Raz extractor. Additionally, we offer an easy-to-use, open-source code implementation of the extractor and a numerical parameter calculation module.
- Abstract（参考訳）: ランダム性抽出器 (Randomness extractor) は、弱いランダムソースをほぼ完全なランダム数に蒸留するアルゴリズムである。
2ソース抽出器は、2つの独立した弱いランダムソースを組み合わせることでこの蒸留プロセスを可能にする。
ラズ抽出器(STOC '05)は、1つの源が直線的なミンエントロピー(すなわち長さに比例する)を持ち、もう1つの源は対数的なミンエントロピーしか持たない環境で最初にこれを達成した。
しかし、ラズの最初の構成は、少なくとも次数 4 の多項式計算時間のために実用的ではない。
本稿では,Razの抽出器の改良版を準線形計算時間で提示し,エントロピー要求を低減した新しい解析定理を提案する。
本稿では, 文献中の他者との構成を包括的に解析・数値的に比較し, 効率的なRaz抽出器の強靭かつ量子耐性バージョンを導出する。
さらに,抽出器のオープンソース実装や数値パラメータ計算モジュールも提供する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - A Fourier Approach to the Parameter Estimation Problem for One-dimensional Gaussian Mixture Models [21.436254507839738]
一次元ガウス混合モデルにおけるパラメータ推定のための新しいアルゴリズムを提案する。
本アルゴリズムは,EMアルゴリズムと比較して,確率,AIC,BICのスコアがよいことを示す。
論文 参考訳（メタデータ） (2024-04-19T03:53:50Z) - Real-Time Seedless Post-Processing for Quantum Random Number Generators [3.9265817364556503]
実時間2ソースの量子ランダム性抽出器を量子側情報に対して導入する。
我々の抽出器は, ミンエントロピー源の新たなカテゴリであるフォワードブロック源に最適化されている。
最もよく使われている量子乱数生成器の生データに抽出器を適用することで、64Gbpsのシミュレーション抽出速度を実現する。
論文 参考訳（メタデータ） (2024-01-29T03:41:07Z) - Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
所望のテレビ距離内において,$d$次元空間にマージンを持つ高次元半空間を学習するためのガウス時間アルゴリズムを提案する。
我々のアルゴリズムはラベルを必要とせず、隠れたハーフスペースのユニークな(そして効率的な)識別性を確立する。
超ポリノミカルな既存のモーメントバウンド保証の代わりに、トータル変分(TV)距離に基づくポリタイム保証を提供することにより、この問題を改善する。
論文 参考訳（メタデータ） (2023-11-02T17:51:10Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。
本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
論文 参考訳（メタデータ） (2023-06-13T01:18:16Z) - Source Identification for Mixtures of Product Distributions [4.893896929103367]
我々は$ n$ビットで$ k$製品分布の混合物のソース識別のためのアルゴリズムを与える。
その結果,これらの混合物のソース同定の計算複雑性に初めて明示的な境界が与えられた。
論文 参考訳（メタデータ） (2020-12-29T00:21:11Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。