Peer Revenue Past citations are no guarantee of future returns

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics

math Watch Mathematics (sign in to use)

Thursday 14 May

Combinatorics

Perturbation of the largest matching root of hypergraphs

The largest matching root of a $k$-graph is the largest real root of its matching polynomial, which is equal to the maximum modulus of all the zeros of the matching polynomial. In this paper, we investigate the perturbation of the largest matching root of $k$-graphs. We determine all $k$-graphs whose largest matching root attains the maximum among all $k$-cacti and linear $k$-cacti with a given number of cycles and edges, where a $k$-cactus is a $k$-graph in which every two distinct cycles have at most one vertex in common. To achieve this, we prove that the celebrated shifting operation of $k$-graphs, introduced by Erdős, Ko and Rado, does not decrease the largest matching root. This result extends a classical result by Csikvári (Electron. J. Combin. 18 (2011) $\#$P182) stating that the Kelmans transformation does not decrease the largest matching root of graphs.
Read the full abstract

Mathematical Physics · Cross-listed from gr-qc

On the catastrophe time of fluids under the action of a gravitational field

Motivated by the central role of the Zel'dovich approximation in the description of cosmic structure formation through gravitational collapse, we investigate Burgers-type dynamics in a spherically symmetric gravitational field. In the Newtonian setting, we derive perturbatively the catastrophe time for radial motion by imposing the loss of invertibility of the Lagrangian map. We show that the perturbative expansion is controlled by the dimensionless parameter $ \alpha=\mu/{r_0^3 v_0(r_0)'^2}, $ rather than by the local gravitational acceleration alone. Hence, the expansion remain valid even when gravity is strong. We then extend the analysis to radial geodesic motion in Schwarzschild spacetime.
Read the full abstract

Representation Theory

Spherical Twists for Gorenstein Orders and $G$-Hilb

This paper constructs derived autoequivalences of Gorenstein orders as twists around spherical functors. More precisely, given a Gorenstein order $A$ and a quotient $p \colon A \to B$, then we specify natural conditions on $B$ under which the twist around the corresponding derived restriction of scalars functor is a derived autoequivalence of $A$. In the process, we show that the associated cotwist is a shift of the Nakayama functor of $B$. These results, together with local-to-global technology, are then used construct new derived autoequivalences for skew group algebras and $G$-Hilbert schemes, and we apply this theory to explicit examples.
Read the full abstract

Group Theory

Commutative decomposition of infinite symmetric groups and transformation monoids

The commutative subgroup width of a group $G$ is the smallest $k$ such that there are abelian subgroups $A_0,A_1,\ldots,A_{k-1}\leq G$ with $G=A_0A_1\cdots A_{k-1}$. Commutative (inverse) submonoid width is defined analogously. In 2002, Abért showed, rather surprisingly, that the commutative subgroup width of the symmetric group on an infinite set is always finite. It was later shown by Seress that it is always bounded above by $14$. We answer a question of Seress and show that in fact the commutative subgroup width of $\operatorname{Sym}(\mathbb{N})$ is at most $9$. We improve the best known lower bound to $4$. We also study standard monoid analogues of the symmetric group; showing that the commutative submonoid widths of the full transformation monoid $\mathbb{N}^\mathbb{N}$, the partial transformation monoid $P_\mathbb{N}$ and the symmetric inverse monoid $I_\mathbb{N}$ are exactly $3$. We conclude by showing that the commutative inverse submonoid width of any infinite symmetric inverse monoid is always infinite.
Read the full abstract

Optimization and Control

A Non-Monotone Preconditioned Trust-Region Method for Neural Network Training

Training deep neural networks at scale can benefit from domain decomposition, where the network is split into subdomains trained in parallel and coupled by a global trust-region mechanism. Building on the Additively Preconditioned Trust-Region Strategy (APTS), we propose a non-monotone variant with a nonlinear additive Schwarz preconditioner that combines parallel subdomain corrections with global coarse-space directions. A windowed acceptance criterion allows controlled objective increases, avoiding needless rejection of effective coarse steps. The resulting non-monotone APTS (NAPTS) preserves accuracy while reducing CPU time by 30% and cutting rejected steps to one third of those in APTS.
Read the full abstract

All authors Andrea Angino, Bindi Çapriqi, Shega Likaj, Ken Trotti, Rolf Krause

Geometric Topology

The Euler obstruction of a $1$-form on a determinantal singularity

In this work, we investigate the connections between the local Euler obstruction and the Poincaré-Hopf-Nash (PHN) index of a $1$-form in the setting of determinantal singularities. As an application, we provide explicit computations of the Euler obstruction of a function with a stratified isolated singularity at the origin defined on an IDS with rigid singularities.
Read the full abstract

Information Theory

Construction of Minimal Ternary Linear Codes with Dimension $m+2$ Via Krawtchouk Polynomials

Recently, minimal linear codes have been extensively studied due to their applications in secret sharing schemes, secure two-party computations, and so on. Constructing minimal linear codes violating the Ashikhmin-Barg condition and then determining their weight distributions have been interesting in coding theory and cryptography. In this paper, a generic construction for ternary linear codes with dimension $m+2$ is presented, where $m$ is an integer, and a necessary and sufficient condition for this ternary linear code to be minimal is derived. Based on this condition and Krawtchouk Polynomials, a new class of minimal ternary linear codes violating the Ashikhmin-Barg condition are obtained, and then their complete weight enumerators are determined.
Read the full abstract

Optimization and Control

Successive convex optimization for transformer encoder model predictive control

We propose a data-driven Model Predictive Control (MPC) framework that employs a transformer encoder to generate multi-step predictions. To handle the nonconvex attention mechanism, we derive difference of convex (DC) representations of the transformer encoder components and embed them in a successive convex programming (SCP) iteration. Recursive feasibility and convergence of the SCP iterates are guaranteed, and each iterate yields a solution estimate satisfying the problem constraints. Under mild assumptions, the SCP iteration converges to a locally optimal solution of the MPC problem. The approach is illustrated on a benchmark nonlinear control problem.
Read the full abstract

Optimization and Control · Cross-listed from cs.LG

In-Context Learning for Data-Driven Censored Inventory Control

We study inventory control with decision-dependent censoring, focusing on the censored or repeated newsvendor (R-NV), where each order quantity determines whether demand is fully observed or censored by sales. Existing approaches based on parametric Thompson sampling (TS) can be brittle under prior mismatch, while offline imputation methods need not transfer to online learning. Motivated by the predictive view of decision making, we combine these ideas by taking oracle actions on learned completions of latent demand. We propose in-context generative posterior sampling (ICGPS), which uses modern generative models that are meta-trained offline and deployed online by in-context autoregressive generation. Theoretically, we show that the Bayesian regret of ICGPS with a learned completion kernel is bounded by the Bayesian regret of a TS benchmark with the ideal completion kernel plus a deployment penalty scaling as $\sqrt{T}$ times the square root of the completion mismatch. This yields a plug-in template for operational problems with known TS regret bounds. For R-NV, we derive sublinear Bayesian regret by reducing censored feedback to bandit convex optimization feedback. We also show that, under reasonable coverage and stability assumptions, the online completion mismatch is controlled by the offline censored predictive mismatch, so offline predictive quality transfers to online performance. Practically, we instantiate ICGPS with ChronosFlow, which combines a frozen time-series transformer backbone with a trainable conditional normalizing-flow head for fast censoring-consistent sampling. In benchmark experiments, ChronosFlow-ICGPS matches correctly specified TS, outperforms myopic and UCB-style baselines, and is robust to prior mismatch and distribution shift. ChronosFlow-ICGPS also performs well for the real-world SuperStore dataset, especially under heavy censoring.
Read the full abstract

All authors Sohom Mukherjee, Anh-Duy Pham, Richard Pibernik, Yunbei Xu

Algebraic Topology · Cross-listed from cs.LG

ToMAToMP: Robust and Multi-Parameter Topological Clustering

Topological clustering, and its main algorithm ToMATo, is a clustering method from Topological Data Analysis (TDA) which has been applied successfully in several applications during the last few years. This is due to its high versatility, as clusters are detected from the persistent components in the sublevel sets of any user-defined function (gene expression, pixel values, etc), and efficiency, as topological clustering enjoys robustness guarantees. However, ToMATo is also limited in several ways. First, a graph on the data points needs to be provided as a hyper-parameter of the method (whose fine-tuning is left to the user). Second, ToMATo is known to be very sensitive to outlier values in the function range. Finally, and most importantly, ToMATo can only handle one function at a time, whereas it is critical to use several functions in various applications. In this article, we introduce ToMAToMP: the first topological clustering method able to handle several functions at the same time with theoretical guarantees. More specifically, we leverage a recent tool from multi-parameter persistent homology, called MMA decomposition, to design our clustering algorithm, and prove that it enjoys robustness properties. As corollaries, we show that it can be used to make ToMATo independent of graph tuning, and robust to outliers. Finally, we provide a set of numerical experiments showcasing the efficiency and quality of the clusterings produced by ToMAToMP, by showing strong improvement over non-topological and topological baselines for various datasets.
Read the full abstract

Information Theory

A class of asymptotically optimal authentication codes with secrecy

In this paper, a class of linear authentication codes with secrecy, which are equipped with simple encoding rules, is constructed. By means of a special Weil sum, the maximum success probabilities of impersonation attack (denoted by $P_I$) and of substitution attack (denoted by $P_S$) for these codes are explicitly derived. It is further proven that the codes are asymptotically optimal, in the sense that both the information theoretic bound and the combinatorial bound for authentication codes are asymptotically attained by $P_I$ and $P_S$.
Read the full abstract

Numerical Analysis · Cross-listed from cond-mat.supr-con

T-E formulation-based modeling of thin HTS shell magnetization

Numerical methods for modeling thin-film magnetization are primarily focused on computing the current density distribution. The highly nonlinear current-voltage characteristic of type-II superconductors significantly complicates the accurate computation of the electric field. The T-E formulation-based mixed finite element method, previously derived for flat superconducting films, enables the simultaneous, accurate determination of both variables. Another advantage of this method is that the computational domain is limited to the film itself: no meshing of the surrounding space is required. The thin-shell approximation reduces the problem to a two-dimensional one. This work extends the T-E formulation and numerical method to non-flat superconducting shells with a metal substrate. We validate the method with several test examples, including modeling the magnetization of a sphere. The method is then applied to a realistic model of a cylindrical magnetic dynamo pump, and the generated open-circuit voltage is computed.
Read the full abstract

Spectral Theory

Reducibility of spectral curves of finite Jacobi pencils

We consider finite pencils of Jacobi matrices \[ J_n(w)=A+wB, \] where $A$ is diagonal and $B$ is tridiagonal with zero diagonal. The spectral curve is the affine plane curve \[ \chi_n(\lambda,w)=\det(\lambda I+J_n(w))=0 . \] The main question is to describe when this curve is reducible. We prove generic irreducibility for fixed pairwise distinct diagonal entries and discuss several elementary reducibility mechanisms. Besides disconnected Jacobi chains, constant eigenvalue branches, and reflection-symmetric components, one must also take into account reducibility caused by scalar diagonal blocks. We formulate a reducibility conjecture and record low-dimensional evidence and counterexamples to several overly optimistic classifications. A central point of the picture is a codimension-growth principle: apart from the cutting divisors $b_i=0$, genuinely connected primitive reducibility should move to higher and higher codimension as the size of the chain grows.
Read the full abstract

Combinatorics

Uniquely 2-colourable 4-cycle decompositions

A cycle system of order $n$ is a decomposition of the edges of the complete graph $K_n$ into cycles of a fixed length. A cycle system is said to be $k$-colourable if we can assign $k$ colours to its vertices so that no cycle is monochromatic. A $k$-colourable cycle system is uniquely $k$-colourable if its colouring is unique up to the permutation of colour classes. In this paper, we construct uniquely $2$-colourable $4$-cycle systems of order $n$ for all admissible $n\geq 49$, and also uniquely $2$-colourable $4$-cycle decompositions of $K_n - I$, for all admissible $n \geq 50$. These constructions contribute to the broader study of uniquely colourable cycle systems and open new directions for future research.
Read the full abstract

Algebraic Geometry

Frobenius–Witt cotangent complexes

We introduce the notion of the Frobenius–Witt cotangent complex, which can be considered as a derived variant of the module of Frobenius–Witt differentials defined by T. Saito. This new object also can be seen as an arithmetic variant of the notion of cotangent complex. We explain the suitability of these two viewpoints through a series of propositions. Furthermore, we establish a relationship between Frobenius–Witt cotangent complexes and the regularity of noetherian local rings, which can be considered as a derived variant of Saito's regularity criterion. This proof relies heavily on computations of Frobenius–Witt cotangent complexes in the case of perfectoid rings. We also study the deformation theory of delta structures using Frobenius–Witt cotangent complexes.
Read the full abstract

2605.14803 · 14 May · 30 pages. Comments are very welcome. v4: corrected the proof of Theorem 5.9. v3: added an application to the deformation theory of delta structures and corrected typos. v2: minor corrections and a generalization of one of the main theorems

Optimization and Control

Avoiding Bias in Clipped SGD for Overparameterized Models under Generalized Smoothness

Modern machine learning is dominated by complex, overparameterized architectures capable of interpolating data and achieving zero training loss. For such models, we investigate the convergence properties of two popular modifications to standard SGD: clipped SGD and normalized SGD. We show that under overparameterization and a mild assumption on batch size, both clipped and normalized SGD do not suffer from the bias typically introduced by clipping, converging effectively at the same rate as their deterministic counterparts. This provides a rigorous theoretical justification for the empirical success of gradient clipping methods. In our analysis, we employ the $(L_0,L_1)$-smoothness condition, under which we obtain convergence rates that improve upon the best known results in prior work. Furthermore, we extend our analysis to specific challenging regimes, including heavy-tailed noise, $(H_0,H_1)$-smoothness (which is strictly weaker than standard assumptions in optimization literature) and the deterministic regime.
Read the full abstract

General Topology

Persistent Homology of Biquandle Coloring Quivers

In this paper, we extend the notion of directed clique complex to quivers and introduce an associated homology theory. By applying this construction to biquandle coloring quivers, we obtain new invariants of links. We then introduce a quiver filtration-valued invariant of links induced by filtrations of biquandle endomorphism sets. We construct persistent homological invariants of links by applying persistence techniques to these quiver filtrations through the introduced homology theory.
Read the full abstract

Differential Geometry

Fredholm Criteria for $G$-pseudodifferential Operators

Let $G$ be a compact Lie group that acts smoothly on a closed manifold $M$. Using a general Simonenko principle, we derive a novel criterion for the Fredholm property of $G$-pseudodifferential operators acting on Sobolev spaces of sections of vector bundles over $M$. In case the group is finite, we obtain a further characterization of the Fredholm property of $G$-pseudodifferential operators in terms of the invertibility of suitable symbols.
Read the full abstract

Complex Variables

The sharp refined Bohr inequalities for a subclass of close-to-convex harmonic mappings

Let $\mathcal{H}$ be the class of normalized complex valued harmonic functions $ f = h + \overline{g}$ defined on the unit disk $\mathbb{D}$, where $h$ and $g$ are analytic functions with the normalization conditions $h(0) = h'(0) - 1 = 0$ and $g(0) = 0$. For the class $R_H^{0}(\gamma, \delta, \lambda)$ ( $0 \leq \lambda < \gamma \leq \delta$) consisting of functions \( f = h+\bar{g} \in \mathcal{H}\) satisfying the condition $f_{\overline{z}}(0)=0$ and the inequality $ Re(\gamma h'(z)+\delta z h''(z) +(\frac{\delta - \gamma}{2})z^2 h'''(z)-\lambda)> |\gamma g'(z)+\delta z g''(z) +(\frac{\delta - \gamma}{2})z^2 g'''(z)|$, we obtain sharp improved Bohr Phenomenon, refined Bohr radius and the Bohr-Rogosinski inequality for the class $R_H^{0}(\gamma, \delta, \lambda)$.
Read the full abstract

Commutative Algebra

On Numerical Semigroups with Fixed Quotient

Let $\Delta$ be a numerical semigroup and let $d\ge 2$ be an integer. We study the fiber of the quotient map \(S\mapsto S/d\) over $\Delta$. We describe its elements as semigroups of the form $\langle X\rangle+d\Delta$, for suitable finite sets $X\subseteq\Delta$, and then analyze explicit and computable regions of this fiber. In particular, we introduce a family $\Delta_d(a)$ of multiples with prescribed quotient and compute its generators, classical invariants, Apéry sets, and presentations. We also show that this construction preserves Wilf's inequality and controls the depth. Finally, we introduce the $\mathcal{M}_d(\Delta)$-rank, determine its maximal value in the fiber, relate it to the ordinary embedding dimension, characterize the rank-one elements, and give closed formulas for their Frobenius-type invariants and pseudo-Frobenius numbers.
Read the full abstract

Numerical Analysis

A Least-Squares Weak Galerkin Finite Element Scheme for Cauchy Problems in Convection–Diffusion

We introduce and rigorously analyze a least-squares weak Galerkin (LS-WG) finite element method for the severely ill-posed Cauchy problem of convection–diffusion equations. The proposed framework utilizes weak derivatives defined on a class of discontinuous weak functions, enabling the natural treatment of complex boundary conditions and internal interfaces. A key advantage of the least-squares formulation is that it transforms the underlying non-self-adjoint operator into a discrete linear system that is inherently symmetric and positive definite (SPD). We demonstrate the geometric flexibility of the method on arbitrary polygonal and polyhedral partitions. Furthermore, we establish the uniqueness of the numerical solution and derive optimal-order error estimates in a carefully defined discrete energy norm. Extensive numerical tests are presented to confirm the theoretical convergence rates and highlight the algorithm's robustness and efficiency compared to standard Galerkin approaches.
Read the full abstract

Numerical Analysis

Eigenbounds of symmetric positive definite tensors

This article introduces an algebraic framework for establishing eigenvalue bounds for symmetric positive definite tensors by leveraging intrinsic invariants, specifically the trace and determinant (resultant). We derive a hierarchy of inequalities via the Arithmetic Mean-Geometric Mean (AM-GM) inequality that yields progressively tighter upper and lower bounds for the tensor spectral radius and smallest eigenvalue. A comprehensive comparative analysis demonstrates that our invariant-based approach significantly outperforms classical coordinate-dependent methods such as the Gershgorin circle theorem. We explicitly show that our bounds remain robust and informative in scenarios where Gershgorin bounds fail, particularly for tensors with negative off-diagonal entries, where algebraic cancellations occur, and higher-order tensors, where combinatorial growth leads to loose estimates. Furthermore, we validate the practical utility of these bounds by applying them to certify the positive definiteness of Lyapunov functions in the stability analysis of nonlinear autonomous systems.
Read the full abstract

Algebraic Geometry

Kuznetsov components ans transcendental motives of cubic fourfolds

Let $X \subset \P^5_{\C}$ be a smooth cubic fourfold.The Kuznetsov component $\sA_X$ is contained in the derived category $D^b(X)$ and the transcendental motive $t(X)$ is contained in the category of Chow motives $\sM_{rat}(\C))$. If $X$ and $Y$ are Fourier -Mukai partners and hence the categories $\sA_X$ and $\sA_Y$ are equivalent, then their transcendental motives $t(X)$ and $t(Y)$ are isomorphic. The aim of this note is to consider families of special cubic fourfolds $X$ with their FM-partners $Y$ and to give an explicit description of the isomorphism between the transcendental motives, in the case $X$ and $Y$ are rational and when they are conjecturally irrational. We also prove that ,for special cubic fourfolds $X $ in countably many Hassett divisors, with a symplectic automorphism of order 3, there exists another special cubic fourfold $Y$, an equivalence of categories $\sA^G_X \simeq \sA_{Y}$, where $\sA^G_X$ is the equivariant Kuznetsov component, and an isomorphism $t(X) \simeq t(Y)$.
Read the full abstract

Statistics Theory · Cross-listed from stat.ME

Differentially private inference framework for Riemannian manifold data

We propose a novel and systematic differentially private (DP) inference framework for non-Euclidean data. First, we design two types of DP mechanisms for the Fréchet mean and variance for i.i.d. Riemannian manifold-valued data, tailored to different geometric structures and accompanied by analytic privacy budgets calibrated to the geometry of the underlying manifold. Second, we establish the consistency and central limit theorems (CLTs) of the proposed DP estimators, enabling a suite of statistical inference procedures under privacy constraints. Furthermore, we provide comprehensive implementation guidelines and feasible procedures, including consistent DP estimators of the asymptotic variance in the CLTs. Extensive numerical experiments support the proposed methodologies. Finally, we demonstrate the effectiveness of our approach on real-world medical image and sociological datasets supported on two representative manifolds.
Read the full abstract

Complex Variables

On Convergence of Rational Hermite-Padé Approximants

The main purpose of this paper is to compare the convergence properties of Padé approximants and rational Hermite-Padé approximants for some model class of multivalued analytic functions based of the inverse Zhoukovsky transform. We prove that in the class of analytic functions under consideration the rational Hermite-Padé approximants converge faster than the corresponding Padé approximants. In contrast to the classical vector potential-theoretic approach, which was introduced by A. A. Gonchar and E. A. Rakhmanov in 1981 and developed later by A. I. Aptekarev, V. N. Sorokin and others, the proofs here are based on some scalar mixed Green-logarithmic potential problems.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

Evolution of Gaussian mixed states under the Markovian master equation for a driven quantum oscillator

We study a generic quantum Markovian master equation for a linearly displaced or driven harmonic oscillator. It was known that the displacement dynamics of Gaussian mixed states depends on the unitary part of the Liouvillian, the decay rate of the system but not on the bath temperature. Here we further show that the fast-rotating modes do not affect the system's displacement dynamics under linear driving forces. Analytical solutions of the quantum master equation are obtained for displaced Gaussian mixed states. Because the non-driven and driven Liouvillians are related by a unitary displacement operator, they are expected to share the same exceptional points structure. At the exceptional points, the displacement of critically damped oscillator displays a characteristics polynomial-in-time prefactor multiplied by an exponential decay. We discuss how external time-dependent forces affect the displacement dynamics using impulsive force and harmonic force as examples. The results obtained for constant driving remain valid in the presence of time-dependent driving.
Read the full abstract

Combinatorics

The spectral radius of $k$-chromatic $r$-graphs

For an $r$-uniform hypergraph $G$, let $\lambda^{(p)}(G)$ denote its $p$-spectral radius, defined as the maximum of the polyform of $G$ over the unit sphere in the $\ell_p$-norm. Let $Q_k^r(n)$ be the complete $k$-chromatic $r$-graph on $n$ vertices with color classes as equal as possible. Kang–Nikiforov–Yuan conjectured that, for every $p\ge1$ and $n>(r-1)k$, the $r$-graph $Q_k^r(n)$ is the unique maximizer of $\lambda^{(p)}$ among all $k$-chromatic $r$-graphs of order $n$. They also conjectured the corresponding explicit bound \[ \lambda^{(p)}(G) \le r!\left(\tbinom nr-k\tbinom{n/k}{r}\right)n^{-r/p}, \] with equality only in the divisible extremal case. The case $r=3$ was established in their work. This paper resolves the remaining cases $r\ge4$, and hence settles both conjectures for all $r\ge3$. As a consequence, the same threshold gives an anti-Wilf-type spectral certificate: any $r$-graph of order $n$ whose $p$-spectral radius exceeds the displayed bound has chromatic number at least $k+1$.
Read the full abstract

Numerical Analysis

Iterative Methods for Computing the T-Square Root of Third-Order Tensors

We develop and analyze iterative methods for computing the principal square root of third-order tensors under the T-product framework. Tensor extensions of the Newton iteration (quadratic convergence) and the Denman–Beavers iteration (geometric convergence with simultaneous computation of the inverse square root) are proposed, with rigorous convergence guarantees established via the Fourier-domain block-diagonalization of the T-product. We apply these methods to image processing, introducing Tensor Decorrelated Grayscale conversion, T-Whitening, and optimal color transfer under the T-product geometry. We also formulate the Tensor Bures–Wasserstein distance and prove it defines a valid metric on the space of T-positive definite tensors. Numerical experiments confirm rapid convergence and demonstrate that the proposed tensor-based techniques offer improved structural preservation and cross-channel decorrelation compared to classical methods.
Read the full abstract

Optimization and Control · Cross-listed from cs.SI

Computing Absorbing-Frequency Centrality: Complexity, Estimators, and Scalable Algorithms for Stochastic Networks

In a stochastic network, where edges fail and weights may vary across realizations, the node of highest betweenness is itself random. Absorbing-frequency centrality (AFC) scores each node by how often it is reported as the node of highest betweenness: the reported betweenness maximizer traces an absorbing Markov chain, and AFC is the normalized expected pre-absorption occupancy. Computing it exactly is intractable: we prove that evaluating even a single transition probability of the AFC chain is #P-hard, by a reduction from two-terminal network reliability, and that the expected absorption time and AFC scores inherit this hardness. We develop a matrix estimator that builds the kernel row-wise and solves one linear system, and a parallelizable episode estimator over absorption trajectories that is strongly consistent and asymptotically normal, with finite-sample guarantees tied to the empirical error decay. A computational study reports scalability on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert graphs, and a monitor placement experiment in which AFC's advantage over pooled counting generally grows with reliability heterogeneity.
Read the full abstract