論文の概要: Leakage-Resilient Extractors against Number-on-Forehead Protocols
- arxiv url: http://arxiv.org/abs/2506.12595v1
- Date: Sat, 14 Jun 2025 18:22:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-17 17:28:46.50284
- Title: Leakage-Resilient Extractors against Number-on-Forehead Protocols
- Title（参考訳）: 前頭数プロトコルに対する漏れ耐性エクストラクタ
- Authors: Eshan Chattopadhyay, Jesse Goodman,
- Abstract要約: 鍵となる要素は、Non-on-forehead (NOF)プロトコルに対するリーク耐性抽出器(LRE)と呼ばれる、新しい擬似ランダムプリミティブをほぼ最適に構築することである。
我々のLREは、Liの低エラー3ソース抽出器(FOCS '15)のより堅牢なバージョンと見なすことができ、Kumar、Meka、Sahaiによるオープンな質問を解決します。
- 参考スコア（独自算出の注目度）: 0.5893124686141781
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a sequence of $N$ independent sources $\mathbf{X}_1,\mathbf{X}_2,\dots,\mathbf{X}_N\sim\{0,1\}^n$, how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC '20), motivated by applications in cryptography, distributed computing, and the unreliable nature of real-world sources of randomness. In their paper, they showed how to construct explicit low-error extractors for just $K \geq N^{1/2}$ good sources of polylogarithmic min-entropy. In a follow-up, Chattopadhyay and Goodman improved the number of good sources required to just $K \geq N^{0.01}$ (FOCS '21). In this paper, we finally achieve $K=3$. Our key ingredient is a near-optimal explicit construction of a new pseudorandom primitive, called a leakage-resilient extractor (LRE) against number-on-forehead (NOF) protocols. Our LRE can be viewed as a significantly more robust version of Li's low-error three-source extractor (FOCS '15), and resolves an open question put forth by Kumar, Meka, and Sahai (FOCS '19) and Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, and Zuckerman (FOCS '20). Our LRE construction is based on a simple new connection we discover between multiparty communication complexity and non-malleable extractors, which shows that such extractors exhibit strong average-case lower bounds against NOF protocols.
- Abstract（参考訳）: N$ 独立なソース $\mathbf{X}_1,\mathbf{X}_2,\dots,\mathbf{X}_N\sim\{0,1\}^n$ の列が与えられたとき、ランダムな文字列を抽出するために、その中の何個が良い(すなわち、いくつかのミンエントロピーを含む)か?
この質問はChattopadhyay、Goodman、Goyal、Li (STOC '20)によって最初に提起された。
彼らの論文では、K \geq N^{1/2}$$の多対数最小エントロピーの優れた情報源に対して、露骨な低エラー抽出器を構築する方法を示した。
その後、ChattopadhyayとGoodmanは、$K \geq N^{0.01}$ (FOCS '21) に必要な良い情報源の数を改善した。
本稿では,最終的に$K=3$を達成する。
我々の重要な要素は、NOFプロトコルに対する漏れ耐性抽出器(LRE)と呼ばれる、新しい擬似ランダムプリミティブをほぼ最適に構築することである。
我々のLREは、Liの低エラー3ソース抽出器(FOCS '15)のより堅牢なバージョンと見なされ、Kumar、Meka、Sahai(FOCS '19)、Chattopadhyay、Goodman、Goyal、Kumar、Li、Meka、Zuckerman(FOCS '20)によるオープンな質問を解決します。
我々のLRE構造は、多人数通信複雑性と非多変数抽出器との間の単純な新しい接続に基づいており、これらの抽出器がNOFプロトコルに対して強い平均値の低い境界を示すことを示している。
関連論文リスト
- New constructions of pseudorandom codes [23.22566380210149]
Pseudorandom error-correcting codes (PRCs) は、生成AIモデルをウォーターマークする新しい暗号プリミティブである。
BKR23]で導入された植込みハイパーループ仮定とGoldreichのPRGホールディングのセキュリティの両方が、効率の良い敵がランダムなコードワードを識別できない公開鍵PRCが存在することを示す。
これは$textitunconditionally$ indistinguishable random by $textpoly()である。
論文 参考訳（メタデータ） (2024-09-11T19:14:39Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Quantum secure non-malleable-extractors [4.527719466355631]
我々はいくつかの明示的な量子安全な非可逆抽出器を構築した。
すべての量子安全な非可算抽出器は、Chattopadhyay, Goyal, Li による構成に基づいている。
論文 参考訳（メタデータ） (2021-09-07T13:56:24Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。