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

• URL: http://arxiv.org/abs/2606.04227v2
• Date: Sat, 06 Jun 2026 00:13:11 GMT
• Title: Incremental Sheaf Cohomology on Cellular Complexes: O(1)-in-n Lazy Edit Processing under Bounded Local Geometry
• Abstract summary: algorithmic framework for incremental maintenance of first sheaf cohomology $H1(X; mathcalF)$ on dynamically evolving 1-dimensional cellular complexes equipped with finite-dimensional cellular sheaves.
• Score: 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.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• One Inverse Step is a Convex Program: Bayes-Limit Calibration of Diffusion Inversion [0.0]
  One implicit DDIM inversion step is the cheapest probe of whether a pretrained diffusion model encodes local manifold geometry.<n>The Fermi window conflicts with the model's own training support by $3.6$-$5.6times$, and the trained Hessian-Lipschitz constant is $2$-$12%$ of the curvature the law reads.<n>Finally the unconditional ceiling $_t_max(mathrmsym,J)le1$, from $mathrmCov(x_0mid x_t)succeq0$
  arXiv  Detail & Related papers  (2026-08-24T11:01:54Z)
• Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts [1.0732935873226024]
  We study ordered prefix computation on $n=2m$ elements of an associative, possibly noncommutative monoid stored in bit-reversed order.<n>A direct transported-predecessor scan uses $mcdot(m+1)/2$ rotations because one logical shift decomposes into several cyclic displacement classes.<n>We instantiate the exclusive scan for radix carry and borrow in bit-reversed CKKS slots, avoiding layout restoration and the final logical-predecessor shift.
  arXiv  Detail & Related papers  (2026-07-03T23:14:45Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Two Layers, No Swaps: Biplanar SPOQC Architecture Improves Runtime of Fermi-Hubbard Simulation [0.0]
  We estimate the cost of simulating the two-dimensional Fermi-Hubbard model on a biplanar spin-optical quantum computing architecture.<n>We benchmark lattice surgery and magic state preparation within each plane.<n>We find that fallback-based rotation synthesis methods become a scalability bottleneck.
  arXiv  Detail & Related papers  (2026-05-06T18:00:09Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  We study numerical integration on $[0,1]$ by quantum amplitude estimation (QAE), focusing on the cost of constructing the amplitude oracle.<n>We introduce a hierarchy of grid function classes $mathcalG_n(d)$, defined by requiring the angle map $_g:0,1nto[0,]$ to be multi of degree at most $d$.<n>For $d=1$ this becomes $O(varepsilon-1log(1/varepsilon))$, improving over classical Monte Carlo for $ge
  arXiv  Detail & Related papers  (2026-04-27T10:23:24Z)
• Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank [14.919427330415608]
  We show that FISTA can improve the dependence on $$ while preserving the $1/$ locality scaling.<n>We analyze FISTA on a slightly over-regularized objective and show that, under a checkable confinement condition, all spurious activations remain inside a boundary set.<n>This yields a bound consisting of an accelerated $(sqrt)-1log(/varepsilon)$ term plus a boundary overhead $sqrtvol(mathcalB)/(3/2)$.
  arXiv  Detail & Related papers  (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]
  We construct a strict hierarchy of temporal layers $C N$ with discrete periods $_N=Nhbar/E$.<n>Each layer is specified by its configuration space, symplectic structure, update rule, and emergent symmetry.<n>We show that these structures follow from discrete-action principles, and that graph growth naturally provides mechanisms for decoherence and spontaneous symmetry breaking.
  arXiv  Detail & Related papers  (2025-11-23T05:25:00Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank computation.<n>We show that the time complexity of such localized methods is upper bounded by $mintildemathcalO(R2/epsilon2), tildemathcalO(m)$ to obtain an $epsilon$-approximation of the PPR vector.
  arXiv  Detail & Related papers  (2025-10-09T09:47:40Z)
• Decentralized Optimization with Topology-Independent Communication [9.348335671378424]
  Distributed optimization requires nodes to coordinate, yet full synchronization scales poorly.<n>This paper proposes randomized local coordination: each node independently samples one regularizer uniformly and coordinates only with nodes sharing that term.<n>Experiments validate both convergence rates and communication efficiency across synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2025-09-17T23:42:57Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.