論文の概要: Quadratic Extractors
- arxiv url: http://arxiv.org/abs/2611.07266v1
- Date: Thu, 05 Nov 2026 00:36:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 21:50:50.477538
- Title: Quadratic Extractors
- Title（参考訳）: 二次エクストラクタ
- Abstract要約: min-エントロピー $k=mathrmpolylog(n)$ に対して明示的な構成を与える。
我々の新しい抽出器は、この障壁をバイパスし、サマセット抽出を超えた最初の明示的な構成を提供する。
- 参考スコア（独自算出の注目度）: 7.4192461394505935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.
- Abstract（参考訳）: 二次元はランダム変数 $X\sim\mathbb{F}_2^n$ で、隠れた一様弦に$n$ 二次体を適用することによって生成される。
以前は、このモデルに対する最もよく知られた明示的抽出器は、約$k=n-\sqrt{\log n}$のミンエントロピーを必要としていた。
本稿では、min-エントロピー $k=\mathrm{polylog}(n)$ に対して明示的な構成を与える。
2$の特別な場合であっても、X$の各ビットは2つの隠れた均一ビットに依存し、$k=\sqrt{n}$以下のエントロピー要件を達成することは重要なオープン問題であった。
これは、サマセット抽出器として知られる、最も強力な汎用シードレス抽出器に(ブラックボックス方式で)確実に還元できないためである。
我々の新しい抽出器は、この障壁をバイパスし、サマセット抽出を超えた最初の明示的な構成を提供する。
関連論文リスト
- Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube [1.4721615285883427]
ランダム入力は予測に不可欠な領域をアンサンプし、モデルが知られている場合でもパラメトリックレートを遅らせる。
ポリアンスキー--サモロディニツキーの不確実性原理を2つの点で研ぎ澄ます。
論文 参考訳（メタデータ） (2026-10-08T17:23:25Z) - Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - Two-Indexed Schatten Quasi-Norms with Applications to Quantum Information Theory [9.048611509540079]
ヒルベルト空間のテンソル積上の作用素上の任意の$q,p > 0$に対して 2-インデックス付き $(q,p)$-Schatten quasi-norms を定義する。
そのような準ノルムの空間間の線型写像に対して、完全有界準ノルムと余準ノルムを導入する。
我々の結果は、逆超収縮性の概念、完全有界最小出力 Rényi-$-entropy for $geqfrac12$ あるいは Sandwiched Rényi Umlaut の情報の加法性を意味する。
論文 参考訳（メタデータ） (2026-04-15T16:35:46Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。
我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文 参考訳（メタデータ） (2022-05-31T17:59:09Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。