skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


This content will become publicly available on August 18, 2026

Title: Nonequilibrium steady-state dynamics of Markov processes on graphs
We propose an analytic approach for the steady-state dynamics of Markov processes on locally tree-like graphs. It is based on time-translation invariant probability distributions for edge trajectories, which we encode in terms of infinite matrix products. For homogeneous ensembles on regular graphs, the distribution is parametrized by a single d×d×r^2 tensor, where r is the number of states per variable, and d is the matrix-product bond dimension. While the method becomes exact in the large-d limit, it typically provides highly accurate results even for small bond dimensions d. The d^2r^2 parameters are determined by solving a fixed point equation, for which we provide an efficient belief-propagation procedure. We apply this approach to a variety of models, including Ising-Glauber dynamics with symmetric and asymmetric couplings, as well as the SIS model. Even for small d, the results are compatible with Monte Carlo estimates and accurately reproduce known exact solutions. The method provides access to precise temporal correlations, which, in some regimes, would be virtually impossible to estimate by sampling.  more » « less
Award ID(s):
2344576
PAR ID:
10631774
Author(s) / Creator(s):
; ;
Publisher / Repository:
SciPost Foundation
Date Published:
Journal Name:
SciPost Physics
Volume:
19
Issue:
2
ISSN:
2542-4653
Page Range / eLocation ID:
045
Subject(s) / Keyword(s):
stochastic network dynamics Ising-Glauber dynamics SIS model message passing algorithms belief propagation tensor network methods matrix product states Bethe lattices
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a truly-subquadratic algorithm of running time O^~(n^{2-1/18}), for finding the diameter in a unit-disk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudo-disks, the graph VC-dimension - either of k-hop balls or the distance encoding vectors - is 4. This contrasts to the VC dimension of the pseudo-disks themselves as geometric ranges (which is known to be 3). Second, we introduce a clique-based r-clustering for geometric intersection graphs, which is an analog of the r-division construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unit-disk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞-disks and fat pseudo-disks of similar size. Last, if the pseudo-disks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter. 
    more » « less
  2. ; ; (, Innovations in Theoretical Computer Science (ITCS 2022))
    For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected d-regular graph with eO( 1 1−λ √ n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree nϵ graphs for any ϵ ∈ (0, 1]) and Cartesian product. 
    more » « less
  3. ; (, Information and Inference: A Journal of the IMA)
    Abstract We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $$Y_{ij} = Z_i^* Z_j^{*T} + \sigma W_{ij}\in{\mathbb{R}}^{d\times d}$$ where $$W_{ij}$$ is a Gaussian random matrix and $$Z_i^*$$ is either an orthogonal matrix or a rotation matrix, and each $$Y_{ij}$$ is observed independently with probability $$p$$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $$(1+o(1))\frac{\sigma ^2 d(d-1)}{2np}$$ when initialized by spectral methods. A matching minimax lower bound is further established that leads to the optimality of the proposed algorithm as it achieves the exact minimax risk. 
    more » « less
  4. ; (, Physical Review B)
    Efficient and accurate computational methods for dealing with interacting electron problems on a lattice are of broad interest to the condensed matter community. For interacting Hubbard models, we introduce a cluster slave-particle approach that provides significant computational savings with high accuracy for total energies, site occupancies, and interaction energies. Compared to exact benchmarks using density matrix renormalization group for d-p Hubbard models, our approach delivers accurate results using two to three orders of magnitude lower computational cost. Our method is based on a slave-particle decomposition with an improved description of particle hoppings, and a density matrix expansion method where the interacting lattice slave-particle problem is turned into a set of overlapping real-space clusters which are solved self-consistently with appropriate physical matching constraints at shared lattice sites between clusters. 
    more » « less
  5. ; (, IEEE)
    The modeling of nonlinear dynamics based on Koopman operator theory, originally applicable only to autonomous systems with no control, is extended to nonautonomous control system without approximation of the input matrix. Prevailing methods using a least square estimate of the input matrix may result in an erroneous input matrix, misinforming the controller. Here, a new method for constructing a Koopman model that yields the exact input matrix is presented. A set of state variables are introduced so that the control inputs are linearly involved in the dynamics of actuators. With these variables, a lifted linear model with the exact input matrix, called a Control-Coherent Koopman Model, is constructed by superposing control input terms, which are linear in local actuator dynamics, to the Koopman operator of the associated autonomous nonlinear system. As an example, the proposed method is applied to multi degree-of-freedom robotic arms, which are controlled with Model Predictive Control (MPC). It is demonstrated that the prevailing Dynamic Mode Decomposition with Control (DMDc) using an approximate input matrix does not provide a satisfactory result, while the Control-Coherent Koopman Model performs well with the correct input matrix, even performing better than the bilinear formulation of the Koopman operator. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email