論文の概要: Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

• arxiv url: http://arxiv.org/abs/2607.03631v1
• Date: Fri, 03 Jul 2026 23:14:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-09 16:16:33.720286
• Title: Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts
• Title（参考訳）: ビット反転同型レイアウトにおける回転最適非可換プリフィックススコープ
• Abstract要約: 我々は、ビット反転順序で格納された連想的、おそらく非可換なモノイドの$n=2m$要素に対する順序付きプレフィックス計算について検討した。 直接輸送前処理スキャンでは、1つの論理シフトが複数の巡回変位クラスに分解されるため、$mcdot(m+1)/2$回転を用いる。 我々は、ビット反転CKKSスロットでラジクスの専用スキャンをインスタンス化し、レイアウトの復元や最終的な論理前処理のシフトを避ける。
• 参考スコア（独自算出の注目度）: 1.0732935873226024
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Packed homomorphic encryption evaluates slotwise operations in parallel, but nonlocal communication is realized by cyclic rotations whose cost depends on the physical slot layout. We study ordered prefix computation on $n=2^m$ elements of an associative, possibly noncommutative monoid stored in bit-reversed order. A direct transported-predecessor scan uses $m\cdot(m+1)/2$ rotations because one logical shift decomposes into several cyclic displacement classes. We introduce a replicated-aggregate invariant: every slot of an aligned logical block stores the same complete block aggregate. Since these copies are semantically interchangeable, one global rotation per level supplies each slot with a valid sibling aggregate, without reaching the exact logical partner. The resulting inclusive or exclusive scan uses $m$ rotations, depth $m$, two live state vectors, and at most $2\cdot m-1$ packed monoid compositions. In a model where all non-routing operations are slotwise and every cyclic rotation invocation is counted, these bounds are exact: $D^\star(m)=R^\star(m)=m$. Equality is rigid: the $m$ offsets contain exactly one representative of each $2$-adic valuation. With at most $K$ directly keyed offsets, we prove a product lower bound and an exact frontier $K\cdot(2^{m/K}-1)$ whenever $K$ divides $m$. We instantiate the exclusive scan for radix carry and borrow in bit-reversed \CKKS slots, avoiding layout restoration and the final logical-predecessor shift. In our implementation at $m=7$, the replicated scan reduces the direct bit-reversed baseline from $28$ to $7$ rotations, lowers evaluation-key storage by $70.0\%$, lowers peak heap usage by $63.9\%$, and improves isolated scan latency by $19.9\%$. In a depth-$5$ downstream pipeline, retaining six additional modulus levels avoids one bootstrap and gives a mean paired speedup of $4.31\times$ with $95\%$ confidence interval $[3.69,4.92]$.
• Abstract（参考訳）: パッケージ同型暗号はスロットワイズ処理を並列に評価するが、物理スロットレイアウトに依存する巡回回転により非局所通信を実現する。 我々は、ビット反転順序で格納された連想的、おそらく非可換なモノイドの$n=2^m$要素に対する順序付きプレフィックス計算について検討した。 直接輸送前処理スキャンでは、1つの論理シフトが複数の巡回変位クラスに分解されるため、$m\cdot(m+1)/2$回転を用いる。 整列論理ブロックの各スロットは同じ完全ブロック集約を格納する。 これらのコピーは意味的に交換可能であるため、各スロットに正確な論理的パートナーに到達することなく、各スロットに有効な兄弟集合を供給している。 最終的な包括的または排他的スキャンは、$m$回転、deep $m$、2つのライブステートベクター、そして少なくとも$2\cdot m-1$充填モノイド合成を使用する。 すべての非ルーティング演算がスロットワイズであり、すべての循環的ローテーションの実行がカウントされるモデルでは、これらの境界は正しい:$D^\star(m)=R^\star(m)=m$。 $m$オフセットは、ちょうど2ドル単位のバリュエーションの1つの代表を含んでいる。 最大で$K$の鍵付きオフセットを持つと、積の下限と正確なフロンティアが$K\cdot(2^{m/K}-1)$のとき、$K$が$m$を割り切ることを証明できる。 我々は、ビット反転した \CKKS スロットでラジクスの専用スキャンをインスタンス化し、レイアウトの復元や最終的な論理前処理のシフトを回避した。 m=7$での我々の実装では、複製スキャンにより、直接ビット反転ベースラインを28ドルから7ドルに減らし、評価キーストレージを70.0\%$、ピークヒープ使用量を63.9\%$に減らし、分離スキャンレイテンシを19.9\%$に改善します。 深さ5ドルのダウンストリームパイプラインでは、追加の6つのモジュラーレベルを保持することで、ブートストラップが1つ回避され、平均的なペアスピードアップが4.31\times$で、信頼区間が9.5\%$[3.69,4.92]$である。

関連論文リスト

• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。 加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
  論文  参考訳（メタデータ） (2026-09-04T18:28:01Z)
• 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)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Incremental Sheaf Cohomology on Cellular Complexes: O(1)-in-n Lazy Edit Processing under Bounded Local Geometry [0.0]
  最初のせん断コホモロジーの漸進的維持のためのアルゴリズム的枠組み:H1(X; MathcalF)$ 有限次元の細胞シーブを備えた動的に進化する1次元細胞複合体について。
  論文  参考訳（メタデータ） (2026-06-02T21:26:02Z)
• Asymmetric Linear-Combination-of-Unitaries Realization of Quantum Convolution via Modular Adders [1.8228930355273179]
  $mathbbZ/NmathbbZ$ 上の円状の畳み込みは、LCU(Line-combination-of-unitaries)フレームワーク内で量子ハードウェア上で実装することができる。 逆行列 $J_n=Xotimes n$ を導入し、反射シフト $widetildeL_i,n=L_i,nJ_n$ を定義する。 結果として生じる対称性演算子は、1つの既知の入力側$J_n$層によってのみ円形の畳み込みとは異なる。
  論文  参考訳（メタデータ） (2026-03-16T12:52:05Z)
• 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)
• Exact Coset Sampling for Quantum Lattice Algorithms [9.910562011343009]
  複雑なガウス窓を持つ最近のウィンドウ付きQFT格子アルゴリズムのステップ9において、競合する「ドメイン拡張」を簡易に置き換える。 我々の新しいサブルーチンは、未知のオフセットを正確にキャンセルするペアシフト差分によってドメイン拡張を置き換える。
  論文  参考訳（メタデータ） (2025-09-15T18:10:28Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit [3.629687485125086]
  位相 $exp(i,f(x))$ を計算基底状態 $left| x right>$ に適用する重要なタスクについて検討する。 また、ターゲット qubit を$f(x)$ に依存する角度で回転させる密接な関連するタスクについても検討する。 実行速度を優先する戦略は,$O(logn+logS)$と$n$ qubitsのレジスタと$S$セクションの断片的な近似に対して,回路深さを$O(logn+logS)$に抑えることができる。
  論文  参考訳（メタデータ） (2024-09-06T19:57:13Z)
• Efficient, direct compilation of SU(N) operations into SNAP & Displacement gates [0.0]
  Map $Phi$は、$d$次元のユニタリを直接SNAPと変位ゲートのシーケンスにコンパイルする機能を提供する。 計算回路上の誤差は各回転を$m$$theta/m$回転に分割することで任意に小さくすることができる。
  論文  参考訳（メタデータ） (2023-07-21T20:58:17Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Deep Learning Meets Projective Clustering [66.726500395069]
  NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。 計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
  論文  参考訳（メタデータ） (2020-10-08T22:47:48Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)

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

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