論文の概要: Incremental Sheaf Cohomology on Cellular Complexes: O(1)-in-n Lazy Edit Processing under Bounded Local Geometry

• arxiv url: http://arxiv.org/abs/2606.04227v2
• Date: Sat, 06 Jun 2026 00:13:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:04.886136
• Title: Incremental Sheaf Cohomology on Cellular Complexes: O(1)-in-n Lazy Edit Processing under Bounded Local Geometry
• Title（参考訳）: 細胞複合体におけるインクリメンタルシーフコホモロジー:O(1)-in-nラジィ編集
• Authors: Jason L. Volk,
• Abstract要約: 最初のせん断コホモロジーの漸進的維持のためのアルゴリズム的枠組み:H1(X; MathcalF)$ 有限次元の細胞シーブを備えた動的に進化する1次元細胞複合体について。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We present an algorithmic framework for incremental maintenance of first sheaf cohomology $H^1(X; \mathcal{F})$ on dynamically evolving 1-dimensional cellular complexes equipped with finite-dimensional cellular sheaves. The classical computation of $H^1$ via factorization of the coboundary matrix requires $O(n^3)$ time; when the complex evolves with a stream of $m$ edits, full recomputation after each edit costs $O(mn^3)$. Under a bounded local geometry assumption -- bounded cell size $v_{\max}$, bounded stalk dimension $d$, and bounded nerve degree $D$ -- each edit (vertex insertion, edge insertion, restriction map update) affects only a bounded set of local coboundary blocks. The algorithm therefore processes lazy streaming edits in $O(1)$ time with respect to the total complex size $n$ (with cost polynomial in the local geometry parameters $v_{\max}$, $d$, and $D$, which are treated as constants independent of $n$), deferring local eigensolves and Mayer-Vietoris global assembly to synchronization points (Flush). At synchronization, the maintained state agrees with the corresponding batch assembly of the partitioned sheaf model; we observe zero measured drift in all batch-verified runs (through $V = 10^6$). We also give an amortized $O(|E|)$ streaming construction for the cellular decomposition and discuss an adversarial algebraic-RAM barrier arguing that unpartitioned non-trivial sheaves ($d \geq 2$, non-identity restriction maps) do not admit the same locality. Experiments on Barabasi-Albert graphs with up to $5 \times 10^6$ vertices and $1.7 \times 10^7$ streaming edits show 35 $μ$s median lazy per-edit update latency (excluding flush); query time (global assembly at synchronization) is $O(n)$ per flush in the implemented full-traversal path. Exact synchronization costs are reported separately.
• Abstract（参考訳）: 有限次元の細胞層を有する動的に進化する1次元細胞複合体上での第一層コホモロジー$H^1(X; \mathcal{F})$の漸増的維持のためのアルゴリズム的枠組みを提案する。 共役行列の分解による$H^1$の古典的な計算は、$O(n^3)$時間を必要とする; 複体が$m$編集のストリームで進化するとき、各編集後の完全再計算は$O(mn^3)$である。 有界セルサイズ$v_{\max}$、有界ストーク次元$d$、有界神経度$D$ -- 各編集(頂点挿入、エッジ挿入、制限マップ更新)は、局所的有界ブロックの有界集合にのみ影響する。 したがってアルゴリズムは、全複素サイズ$n$(局所幾何学パラメータ$v_{\max}$,$d$,$D$)に関して、遅延ストリーミング編集を$O(1)$時間で処理し、局所固有解とMayer-Vietorisグローバルアセンブリを同期点(Flush)に延期する。 同期時には、維持状態は分割棚モデルの対応するバッチ集合と一致し、全てのバッチ検証実行において($V = 10^6$で)ゼロのドリフトが観測される。 また、セル分解のストリーミング構成に$O(|E|)$の償却を与えるとともに、非分割非自明な層(d \geq 2$, non-identity limit map)が同じ局所性を認めないと主張する逆代数的-RAM障壁について議論する。 Barabasi-Albert グラフの最大5ドル (10^6$) の頂点と1.7ドル (10^7$) のストリーミング編集による実験では、中央値の遅延が35$μ$s (hashを除く)、クエリ時間 (同期時のグローバルアセンブリ) はフルトラバーサルパスで1フローあたり$O(n)$である。 正確な同期コストは別々に報告される。

関連論文リスト

• Two Layers, No Swaps: Biplanar SPOQC Architecture Improves Runtime of Fermi-Hubbard Simulation [0.0]
  二平面スピン光学量子コンピューティングアーキテクチャ上での2次元フェルミ・ハバードモデルのシミュレーションコストを推定する。 各平面内における格子手術とマジック状態準備のベンチマークを行った。 フォールバックに基づく回転合成法はスケーラビリティのボトルネックとなる。
  論文  参考訳（メタデータ） (2026-05-06T18:00:09Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank [14.919427330415608]
  FISTAは1/$ローカリティスケーリングを保ちながら$$への依存を改善することができることを示す。 我々はFISTAをわずかに過正規化された目的に基づいて解析し、チェック可能な閉じ込め条件下では、全ての刺激活性化が境界集合内に存在することを示す。 これにより、加速された$(sqrt)-1log(/varepsilon)$項と境界オーバーヘッド$sqrtvol(mathcalB)/(3/2)$からなるバウンダリが得られる。
  論文  参考訳（メタデータ） (2026-02-24T17:35:46Z)
• Discrete Action, Graph Evolution, and the Hierarchy of Symmetries: A Rigorous Construction of Temporal Layers $C1 \to C2 \to C3 \to C4$ [0.0]
  我々は、離散周期を$_N=Nhbar/E$とする時間層$C N$の厳密な階層を構築する。 各層は構成空間、シンプレクティック構造、更新規則、創発対称性によって指定される。 これらの構造は離散的な作用原理に従っており、グラフの成長は自然に非一貫性と自発的対称性の破れのメカニズムを提供する。
  論文  参考訳（メタデータ） (2025-11-23T05:25:00Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
  論文  参考訳（メタデータ） (2025-10-09T09:47:40Z)
• Decentralized Optimization with Topology-Independent Communication [9.348335671378424]
  分散最適化にはノードの調整が必要ですが、完全な同期スケールは不十分です。 本稿では,各ノードが一意に1つの正規化器をサンプリングし,その項を共有するノードのみを協調するランダム化局所調整を提案する。 実験は、合成データセットと実世界のデータセット間の収束率と通信効率の両方を検証する。
  論文  参考訳（メタデータ） (2025-09-17T23:42:57Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)

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

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