CS Paper Radar

Directed walks shape a universal square-root law of entropy production rate in nonreciprocal systems

Thiparat Chotibut, Ewa Gudowska-Nowak, Maciej A. Nowak

cs.NE cond-mat.stat-mechcond-mat.dis-nnmath-phq-bio.NC ·submitted 2026-08-25 18:18 UTC · v1
unusual

Abstract

The entropy production rate (EPR) quantifies irreversibility of a nonequilibrium steady state, yet standard formulas obscure how a complex interaction network generates it. For multivariate Ornstein-Uhlenbeck dynamics on such networks, we express the EPR as a quadratic form in antisymmetric matrices measuring the nonreciprocity of aggregate directed walks at every length, and, equivalently, as two weighted-walk quantities: pairs of directed walks sharing both endpoints, and directed closed walks. For diagonalizable interactions, an exact correspondence translates these walk quantities into eigenvalues and biorthogonal eigenvector overlaps. Across dense, sparse, and deep acyclic random interactions satisfying matched-walk conditions, the mean EPR per node universally follows the square-root law $φ_*(g)=1-\sqrt{1-g^2}$, where $g \in [0,1)$ parametrizes the interaction strength. Deep acyclic interaction matrices are nilpotent, with all eigenvalues fixed at zero for every $g$, yet, as their depth increases, their mean EPR per node approaches $φ_*(g)$. Thus, the square-root law arises from directed walk properties, rather than from a shared spectral density or specific network topology.

Comment
9 pages, 2 figures. Supplemental Material submitted for peer review will be made publicly available following peer review

Closest papers

Nearest neighbours by meaning across the whole index.

Resource competition and survival for random walkers on complex networks

cs.SI physics.comp-phstat.AP ·2026-10-24 ·Snehal Shekatkar
similarity 0.53
Abstract · 4 pages, 4 figures

We consider the problem of $W$ random walkers on a complex network where each walker requires an amount $θ$ of resource at each time to survive. Resource is stochastically produced at each vertex of the network with a specified distribution. The survival time of the system of walkers is defined as the time required for all $W$ walkers to die. Using numerical simulations, we show that Erd{\H o}s-Rényi networks a have higher mean survival time than Scale-free networks as expected, but also that uniform distribution production leads to higher mean survival time than exponential distribution with the same mean. We derive an exact expression for the survival-time distribution under the assumption of independent walker lifespans, and use it to show that scale-free network topology produces strong dependence in the lifespans but homogeneous topology does not. We moreover demonstrate how the survival time can be substantially increased without changing the resource production or network topology by appropriately biasing the movement of the walkers towards low degree vertices on Scale-free networks, but has no effect on Erd{\H o}s-R{é}nyi networks.

0.27

On the Spectral Dependence of Decentralized Stochastic Gradient Tracking

eess.SY math.OC ·2026-11-05 ·Sulaiman A. Alghunaim, Haoyuan Cai, Ali H. Sayed
theory similarity 0.52
Abstract

We study how the spectral geometry of the mixing matrix enters the convergence of decentralized stochastic gradient tracking (GT) for smooth strongly convex problems. General bounds contain the factor $Δ_λ^{-3}$ in the higher-order stochastic term, where $Δ_λ$ is the absolute spectral gap. We show that, even for two agents with identical quadratic objectives, the exact steady-state mean-square disagreement scales as $α^2σ^2Δ_λ^{-3}$ as the nontrivial eigenvalue approaches $-1$, provided the stepsize $α$ is sufficiently small relative to the gap. Here $σ^2$ is the gradient-noise variance. By unrolling the disagreement recursion, we establish a stochastic bound that averages all nontrivial eigenvalue contributions for diagonalizable mixing matrices, up to an eigenvector conditioning factor. As a real or complex eigenvalue approaches the unit circle away from $1$, its contribution grows as the inverse cube of its distance to the circle; growth can be slower near $1$. For symmetric mixing with gaps $p$ at $1$ and $ν$ at $-1$, the weighted sum $θ_1/p+θ_2/ν^3$ replaces the prior factor $(Δ_λν^2)^{-1}$. For $N$ agents, $Nθ_1$ and $Nθ_2$ count the nonnegative and negative nontrivial eigenvalues, respectively. On a symmetric family, a finite-horizon lower bound for the average iterate matches the worst-case factor $p^{-1}+ν^{-3}$ up to universal constants. Numerical experiments confirm the predicted scaling.

0.22

A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra

cs.DS stat.ML ·2026-08-26 ·Zhao Song, Lichen Zhang
similarity 0.52
Abstract

We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together. Their leading uncentered terms cancel in the complete logarithmic acceptance ratio, leaving centered fluctuations that can be controlled with second-order tools. For a polytope given by $n$ inequalities and a convex $L$-Lipschitz potential, this yields warm-start mixing in $\widetilde O((d^{2}+dL^{2}R^{2})\log(w/δ))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((ψ^\star nd+dL^{2}R^{2})\log(w/δ))$ steps, where $ψ^\star$ measures matrix leverage. The two analyses share an acceptance-to-mixing reduction. A proposal-comparison argument transfers the polytope bound to an appropriately padded $O(1/d)$-accurate metric computed from high-precision Lewis weights. For spectrahedra, given $\widehatψ\geψ^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $ψ^\star$ replaced by $\widehatψ$ in the mixing bound.

0.12

Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields

cs.CR ·2026-11-03 ·Mark Braverman, Aayush Jain, Stephen Newman
hot direction similarity 0.52
Abstract

\emph{Trapdoored matrices} are pseudorandom matrices admitting a fast matrix-vector multiplication algorithm given the secret key. We study a candidate family of such matrices: matrices generated by short random \emph{transvection walks} on \(\mathrm{SL}_n(\mathbb{F}_q)\), whose steps are given by adding a random multiple of a random row of the current state to another. We show that the worst-case time for any nonempty set \(\mathcal{S}\subseteq [n]\times[n]\) of matrix entries to come within TV distance \(\varepsilon\leq \frac{1}{4}\) of its stationary marginal under this walk is \(Θ(|\mathcal{S}|+n\log(n/\varepsilon))\), uniformly over all \(\mathcal{S}\) and \(q\geq Q_\mathrm{all}(n)\). This is asymptotically optimal, and resolves open questions about the mixing times of transvection walks. We derive concrete upper and lower bounds for \(n\geq 256\). Surprisingly, our bounds also hold conditioned on the row-pair structure of the walk, except on a fraction at most \(\varepsilon\) of such structures. This implies that these walks may be pseudorandom even after conditioning on the row-pair structure, and therefore that trapdoored matrices built with these walks may be universal. Assuming the conjectured structure-conditioned pseudorandomness of short walks, we exhibit highly efficient, highly parallelizable, and universal trapdoored matrices over \(\mathrm{SL}_n(\mathbb{F}_q)\), \(\mathrm{GL}_n(\mathbb{F}_q)\), and \(\mathbb{F}_q^{n\times n}\). The families over \(\mathrm{SL}_n(\mathbb{F}_q)\) and \(\mathrm{GL}_n(\mathbb{F}_q)\) admit equally efficient trapdoors for their inverses, making them the first to do so for finite-field trapdoored matrices. We discuss attacks, analyzing one in detail, and lay out directions for further investigation.

0.35

Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis

cs.DS cs.DMmath.COmath.PR ·2026-09-17 ·Xiaoyu Chen, Kuikui Liu
theoryhighly cited similarity 0.52
Abstract

Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders. One of the most striking results in this burgeoning literature is that a spectral gap for the global down-up walk on the facets of a pure simplicial complex can be reduced to sufficiently strong spectral expansion of just the codimension-2 links of the complex, a phenomenon colloquially referred to as "trickle-down". These types of theorems have had many important applications, including rapid mixing of the exchange walk on the bases of any matroid. In this primarily expository article, we give streamlined proofs of two such theorems in the literature, one by Oppenheim (2018) and one by Leake and Oveis Gharan (2025), via an integrated Bochner method. Moreover, in the latter setting, we quantitatively strengthen the dependence of the global spectral gap on the dimension of the complex and the spectral influence, resolving an open question of Leake and Oveis Gharan. Disclaimer: The proofs were developed through a couple of rounds of interaction with GPT-5.6 Sol Ultra. We later discovered that Guo and Zhang (2026) had independently proven the same strengthening of the trickle-down theorem of Leake and Oveis Gharan using an extremely similar argument, also found by GPT-5.6 Sol Ultra. The focus of their paper is the complexity of approximating the partition function of spin systems on planar graphs, not on the trickle-down phenomenon itself. In contrast, our motivation is primarily expository, and we hope to bring Bochner-type methods and their connections with the trickle-down phenomenon to the attention of a wider community of researchers.

0.49

Efficiency--Complexity Tradeoff and Constrained Percolation

eess.SY math.PRmath.COq-bio.NC ·2026-10-24 ·Yuliy Baryshnikov, Efe Onaran
similarity 0.52
Abstract · 27 pages, 2 figures

We study the efficiency--complexity tradeoff for resource-limited agents through directed first-passage percolation. Nonnegative i.i.d. edge weights represent physical energy expenditure, while the logarithmic size of a constrained path family measures representational complexity. For translation-invariant families, a path-joining property yields deterministic large-distance costs in rational directions and joint convexity in constraint parameter and direction, under suitable moment and feasibility assumptions. Our main result concerns the limiting cost parameterized by path-family entropy. Using techniques from analytic combinatorics in several variables (ACSV), we establish its almost-sure existence and joint continuity in entropy and direction for nested families satisfying additional generating-function conditions, on the corresponding entropy range. Path-count asymptotics supply the change of parameter linking this cost to the constraint-parameterized cost. Two planar examples constrain the number of turns or the number of East-runs of length at least two.

0.31

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β\leq \frac{1}{2}+\varepsilon$

cs.DS math-phmath.PR ·2026-09-11 ·Mathews Boban, Anqi Li, Shayan Oveis Gharan
similarity 0.51
Abstract · 34 pages

We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by $λI$ (where $λ$ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for $β\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.

0.39

Fully Dynamic Random-Walk Quantities on Undirected Expanders and $κ$-Uniform Directed Graphs

cs.DS ·2026-10-13 ·Richard Peng, Sushant Sachdeva, Junzhao Yang, Yibin Zhao
similarity 0.51
Abstract

We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has spectral gap at least $γ$, we give a $(1\pm\varepsilon)$ effective-resistance data structure with expected update time $O(γ^{-4}\varepsilon^{-2}\log n\log^4(n/\varepsilon))$ and expected $O(1)$ query time. For directed graphs, somewhat surprisingly, the OMv conjecture precludes a fast data structure based on rapid mixing conditions alone. To address this, we introduce the notion of $κ$-uniform directed graphs, which requires the stationary distribution to $κ$-approximate the uniform distribution, and show that in this setting, random walk based data structures with $\text{poly}(κ, \log{n}, \varepsilon^{-1})$ update/query times are possible.

0.21