The Solvability Complexity Index (SCI) provides an extensional limit-height formalism for recovering a target map $Ξ$ from finite samples of an evaluation interface $Λ\subseteq\mathbb C^Ω$ by finite-height towers of pointwise limits. We first give a foundational analysis of what this extensional framework does and does not determine. In second place, we give a concrete non-trivial bridge result from a comparable SCI object to the well known limit rank of Weihrauch theory.
Shane E. Loeffler, Zan Ahmad, Shiyi Chen, Syed Yusuf Ali, Carolyna Yamamoto, Kensuke Sakata, Dan M. Popescu, Alana Yee 等 11 位作者
原文摘要
High-fidelity simulations of time-dependent nonlinear partial differential equations (PDEs) are expensive to repeat across families of domains and parameter fields, a cost that recurs in design optimization, uncertainty quantification, and computational medicine. Most neural-operator surrogates require each domain to be mapped onto a common grid or reference shape, and few predict the full time course. We introduce Graph Fourier Neural Kernels (G-FuNK), a neural operator for second-order semilinear PDEs with a diffusive principal part that transfers across geometries and anisotropic diffusion tensors without coordinate maps or diffeomorphisms. A weighted graph and its Laplacian supply a spectral basis that encodes geometry and anisotropy. Shared layers act in this basis, at a cost linear in mesh size after one partial eigendecomposition per geometry, and a neural ODE integrator propagates the learned generator to full spatiotemporal trajectories on unseen domains. Across anisotropic heat flow, stiff reaction-diffusion, FitzHugh-Nagumo, and patient-specific left-atrial electrophysiology on CT-derived surfaces, G-FuNK reproduces held-out trajectories with relative $L^2$ error between 0.046 and 0.160. Its accuracy is comparable to that of a geometry-aware Fourier neural operator on regular domains, and its predictions are unchanged when a rectangular domain is rotated. On left atria, whose venous and valvular openings prevent mapping onto a reference shape, it predicts an 85-ms trajectory in under half a second, against about 5 minutes for finite elements, with a mean activation-time error of 1.73 ms. Accuracy depends on graph construction and is highest when the learned generator is integrated at its training time step.
Spectral graph sparsification is a classical tool for reducing graph complexity while preserving Laplacian quadratic forms. In graph neural networks (GNNs), sparsification is often used to accelerate computation while maintaining predictive performance. In this work, we study a complementary representation-level question: does sparsification preserve the geometry of learned embeddings? For polynomial-filter GNNs, we prove that any $ε$-spectral sparsifier induces $O(ε)$ perturbations in polynomial graph filters, multilayer hidden representations, and their Gram matrices. These guarantees imply stability of squared pairwise distances, class means, and covariance structure in embedding space. We further establish finite-time training stability: under smoothness and boundedness assumptions, gradient descent on dense and sparsified graphs produces weight trajectories whose separation grows at most proportionally to the sparsification distortion. Empirically, effective-resistance sparsification validates the predicted perturbation chain on synthetic graphs and preserves hidden representation geometry on real datasets. In our experiments, the gram matrix and training dynamics show low divergence even under substantial sparsification, consistent with the predicted stability under spectral sparsification. Hidden Gram preservation strongly predicts neighborhood preservation and class-centroid stability across FashionMNIST, Cora, and Paul15. Together, these results show that spectral sparsification preserves not only graph operators, but also the representation geometry that supports downstream use of GNN embeddings for interpretability.
The Fast Tree Transform is a locally-aggregated transform defined for arbitrary graph geometries that generalizes both the Hadamard frequency transform and the Haar wavelet transform on the circle. The pure frequency part of the transform approximately diagonalizes the graph Laplacian; this fact makes it useful as a preconditioner in geometric optimization problems. The full transform provides an only slightly-redundant representation of signals on the graph that allows sparse representation of signals that include both edges and textures.
Persistent homology (PH) summarizes the topological features of data that persist across scales, but it is insensitive to many geometric properties. Persistent Laplacians (PLs) address this limitation: for a pair of simplicial complexes in a filtration, the kernel of the persistent Laplacian recovers the persistent Betti number, while its non-zero spectrum carries additional geometric information. However, PLs are defined for individual pairs of filtration values, so analysing a whole filtration requires evaluating many operators that largely contain the same information, and the result is hard to summarize and interpret. In this paper, we show that this redundancy has a precise structure. For each pair of filtration values, we decompose the space of chains underlying the persistent up-Laplacian into the contributions inherited from the neighboring pairs and a remaining part, which we call the new persistent chain space. We show that the new persistent chain spaces of all earlier pairs form a direct sum decomposition of this space, so that every persistent up-Laplacian in the filtration is determined by them. Moreover, the new persistent chain spaces are non-trivial only at pairs given by the persistence pairing in the same and in the next homological dimension, so that the persistence pairing determines exactly where the persistent up-Laplacian can change. Experiments on several types of point clouds show that evaluating persistent Laplacians only at these pairs reduces the computation time, both for our implementation and for existing software.
Emma Reyner-Fuentes, Sebastian Rudolph, Carmen Peláez-Moreno, Francisco J. Valverde-Albacete
原文摘要
Brains do not simply add up every signal they receive: they select which routes dominate. Yet connectomes are usually analyzed with tools that sum over all paths and place neural states in Euclidean spaces, blurring the feedback circuits that may sustain internal states. Here we treat neural signaling as routing instead of diffusion and describe it with max-plus algebra, in which signals accumulate along a path and the strongest route prevails. We propose a model in which the functional connectome of Caenorhabditis elegans emerges from the time-varying combination of electrical, synaptic, monoaminergic, neuropeptidergic and hormonal layers, and analyze five networks within this framework. Each collapses onto a handful of dominant feedback loops, which recover well-characterized circuits and point to new candidates for experimental study. Unlike linear spectra, these structures keep the biological meaning of the data, and their order-based description suggests that brain states live in lattices rather than Euclidean spaces.
Priyanka Grover, Hemant K. Mishra, Sarishti Singh, Temjensangba
原文摘要
The symplectic interlacing theorem states that the symplectic spectrum of a $2n \times 2n$ real symmetric positive definite matrix satisfies a $2k$-step interlacing relation with the symplectic spectrum of every $2(n-k) \times 2(n-k)$ $s$-principal submatrix. We prove the converse in this paper. More precisely, given a positive global symplectic spectrum of size $n$ and a positive local symplectic spectrum of size $n-k$ satisfying the $2k$-step interlacing inequalities, we construct a $2n \times 2n$ real symmetric positive definite matrix having the prescribed global symplectic spectrum and a $2(n-k) \times 2(n-k)$ $s$-principal submatrix of it having the prescribed local symplectic spectrum. Our main tool is a reduction of $s$-principal compression to a rank-$k$ singular value perturbation. In the context of the Gaussian quantum marginal problem, our result implies that the symplectic interlacing inequalities are not merely necessary conditions on Gaussian marginals, but are also the complete spectral compatibility conditions for the global-versus-local-mode marginal problem.