論文の概要: Nearly-Linear Time Seeded Extractors with Short Seeds

• arxiv url: http://arxiv.org/abs/2411.07473v1
• Date: Tue, 12 Nov 2024 01:19:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-13 13:19:47.058689
• Title: Nearly-Linear Time Seeded Extractors with Short Seeds
• Title（参考訳）: 近赤外種近近近近距離種子外子
• Authors: Dean Doron, João Ribeiro,
• Abstract要約: 種子長と出力長の大きい種子抽出機の既設構造を時間内に実行した。 本研究では, コンデンサと古典的手法を併用して, 高ミンエントロピー源のシード抽出器を構築することにより, 強い抽出器が得られることを示す。 また、RAMモデルにおいて真に線形時間で評価できるトレビサン抽出器のインスタンス化を行う。
• 参考スコア（独自算出の注目度）: 9.896415488558036
• License:
• Abstract: (abstract shortened due to space constraints) Existing constructions of seeded extractors with short seed length and large output length run in time $\Omega(n \log(1/\varepsilon))$ and often slower, where $n$ is the input source length and $\varepsilon$ is the error of the extractor. Since cryptographic applications of extractors require $\varepsilon$ to be small, the resulting runtime makes these extractors unusable in practice. Motivated by this, we explore constructions of strong seeded extractors with short seeds computable in nearly-linear time $O(n \log^c n)$, for any error $\varepsilon$. We show that an appropriate combination of modern condensers and classical approaches for constructing seeded extractors for high min-entropy sources yields strong extractors for $n$-bit sources with any min-entropy $k$ and any target error $\varepsilon$ with seed length $d=O(\log(n/\varepsilon))$ and output length $m=(1-\eta)k$ for an arbitrarily small constant $\eta>0$, running in nearly-linear time, after a reasonable one-time preprocessing step (finding a primitive element of $\mathbb{F}_q$ with $q=poly(n/\varepsilon)$ a power of $2$) that is only required when $k<2^{C\log^* n}\cdot\log^2(n/\varepsilon)$, for a constant $C>0$ and $\log^*$ the iterated logarithm, and which can be implemented in time $polylog(n/\varepsilon)$ under mild conditions on $q$. As a second contribution, we give an instantiation of Trevisan's extractor that can be evaluated in truly linear time in the RAM model, as long as the number of output bits is at most $\frac{n}{\log(1/\varepsilon)polylog(n)}$. Previous fast implementations of Trevisan's extractor ran in $\widetilde{O}(n)$ time in this setting. In particular, these extractors directly yield privacy amplification protocols with the same time complexity and output length, and communication complexity equal to their seed length.
• Abstract（参考訳）: (空間制約により短縮) 短いシード長と大きな出力長を持つシード抽出器の構成は、時間で$\Omega(n \log(1/\varepsilon)$で、しばしば遅くなるが、$n$は入力ソース長、$\varepsilon$は抽出器のエラーである。 抽出器の暗号的応用は$\varepsilon$を小さくする必要があるため、結果として得られるランタイムは、実際にこれらの抽出器を使用不能にする。 これにより, ほぼ直線時間で計算可能な短い種子を持つ強い種子抽出器の構成を, 任意の誤差に対して$O(n \log^c n)$で探索する。 任意の最小エントロピー$k$と任意のターゲット誤差$\varepsilon$と、任意の最小エントロピー$d=O(\log(n/\varepsilon))$と出力長$m=(1-\eta)k$を任意に小さな定数$\eta>0$とすることで、任意の1時間前処理ステップ($\mathbb{F}_q$と$q=poly(n/\varepsilon)$のプリミティブ要素を$q=poly(n/\varepsilon)$と$2$の出力しか必要としない場合にのみ、$2$の出力を出力する。 2つ目の貢献として、出力ビットの数が最大$\frac{n}{\log(1/\varepsilon)polylog(n)}$である限り、RAMモデルにおいて真の線形時間で評価できるトレビサンの抽出器のインスタンス化を与える。 トレビサンの抽出器の以前の高速な実装は、この設定で$\widetilde{O}(n)$ timeで実行された。 特に、これらの抽出器は、時間的複雑さと出力長、および通信の複雑さがシード長に等しいように、直接、プライバシー増幅プロトコルを出力する。

関連論文リスト

• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
  安定度が低い」量子状態は、Haar-randomと効率的に区別できることを示す。 我々は、計算的に擬似ランダムな量子状態を作成するためには、任意のクリフォード+$T$回路に対して$omega(log(n))$$T$-gatesが必要であることを証明した。
  論文  参考訳（メタデータ） (2022-09-29T03:34:03Z)
• Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
  サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。 これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
  論文  参考訳（メタデータ） (2022-05-19T18:51:28Z)
• Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem [8.34061303235504]
  我々は、シミュレートされたアニーリングが、時間内の最小スパンニングツリー問題に対して、任意に厳密な定数係数近似を計算することを証明した。 任意の$epsilon>0$に対して、$O((mnln(n))1+1/epsilon+o(1)(lnln n + ln(T_0/w_min))$を少なくとも1-1/m$の確率で選ぶことができる。
  論文  参考訳（メタデータ） (2022-04-05T10:22:31Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。 次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
  論文  参考訳（メタデータ） (2020-06-21T06:57:59Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。