論文の概要: Uncertainty Principles for the Number Theoretic Transform

• arxiv url: http://arxiv.org/abs/2606.08662v1
• Date: Sun, 07 Jun 2026 15:05:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:06.364481
• Title: Uncertainty Principles for the Number Theoretic Transform
• Title（参考訳）: 数理論変換の不確かさ原理
• Authors: Giulio Malavolta, Alon Rosen,
• Abstract要約: 指数関数を用いたアイデンティティテストによって動機付けられた数理論変換(NTT)の不確実性原理について研究する。 我々はNTTが強いスパシティトレードオフを満足していることを示します。 アプリケーションとして、$k$よりも適度に大きい$q$に対して、音質誤差が消えることなく、$k$スパース$指数の指数を最大$d$とするブラックボックスIDテストを得る。
• 参考スコア（独自算出の注目度）: 14.160141867381695
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by polynomial identity testing with exponentials (Li and Wu, ITCS'26), we study uncertainty principles for the number-theoretic transform (NTT). We show that the NTT satisfies strong sparsity tradeoffs: For every fixed prime $q$ and for all but finitely many primes $p \equiv 1 \pmod q$ every nonzero $f\in \mathbb F_p^{\mathbb Z_q}$ and its number-theoretic transform $\hat f$ satisfy \[ |\mathrm{Supp}(f)| + |\mathrm{Supp}(\hat f)| \ge q+1. \] Thus, a $k$-sparse function has transform support at least $q-k+1$. As our main technical contribution, we prove a probabilistic version of the above uncertainty principle, averaged over primes $p$, in the regime $p=q^{O(1)}$. As an application, we obtain a black-box identity test for $k$-sparse exponential polynomials of degree at most $d$ with vanishing soundness error, for $q$ moderately larger than $k$.
• Abstract（参考訳）: 指数関数を用いた多項式アイデンティティテスト(Li and Wu, ITCS'26)により動機付け, 数理論変換(NTT)の不確実性原理について検討した。 すべての固定素数$q$と有限個の素数$p \equiv 1 \pmod q$すべての非零数$f\in \mathbb F_p^{\mathbb Z_q}$とその数論変換 $\hat f$ は \[|\mathrm{Supp}(f)| + |\mathrm{Supp}(\hat f)| \ge q+1 を満たす。 したがって、$k$-sparse関数は少なくとも$q-k+1$の変換サポートを持つ。 我々の主要な技術的貢献として、上記の不確実性原理の確率バージョンを証明し、素数$p=q^{O(1)}$で平均して$p$である。 応用として、$k$よりも適度に大きい$q$の音響誤差を伴って、次数$d$の指数多項式を最大$d$でブラックボックス識別テストを得る。

関連論文リスト

• Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE [0.0]
  PRIM-LWE問題はLearning with Errors問題の変種であり、秘密行列はプリミティブ・ルート行列式を持つ必要がある。 素数上の$c(p)$の極限分布は、正確に$[0,1/2]$であることを示す。 また、暗号的興味を持つ素数に対して$c(q)$の明示的な下限を導出し、q-1$の別個の素数だけによってパラメータ化する。
  論文  参考訳（メタデータ） (2026-03-11T18:04:48Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
  論文  参考訳（メタデータ） (2026-03-09T22:27:00Z)
• An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
  有限体 $mathbbF_q2$ は$q2$ 要素からなる。 まず、いくつかの重要な単純化を取り入れた電力関数 $f(x) = xq+2$ on $mathbbF_q2$ の微分スペクトルを決定する方法を提案する。
  論文  参考訳（メタデータ） (2024-07-08T14:01:06Z)
• Some new infinite families of non-$p$-rational real quadratic fields [0.0]
  同時に、$p_j$-有理実体の無限族を構成するための単純な方法論を与え、$p_j$の任意の上を無理化する。 これらの技法の1つの特徴は、素体$K=mathbbQ(sqrtD)$を、極大アーベル群のガロア群のトーション群の$p$パワー巡回成分である$p$を超える非有理な外部素数の$K$が$paであるような体を与えるのに使用できることである。
  論文  参考訳（メタデータ） (2024-06-20T18:00:51Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• 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)
• Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
  mathbb Cd$ の正則基底の集合 $k$ は互いに非バイアスな $|langle e,frangle |2 = 1/d$ と呼ばれ、$e$ と $f$ は異なる基底の基底ベクトルである。 この対称性を(解析的に)利用して、半定値プログラムのサイズを縮小し、取り外し可能とする。
  論文  参考訳（メタデータ） (2021-11-10T14:14:53Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)

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

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