Marek Jankola

We investigate how much bias in the initial configuration is required to drive global agreement in synchronous, deterministic majority dynamics on large random d-regular graphs. Nodes take values ±1 and update their states at each discrete time step to align with the majority of their neighbors. Using the backtracking dynamical cavity method (BDCM), we estimate the minimal fraction of initial +1 nodes required to achieve a +1 consensus in p time steps. Our analysis predicts that for d ≥ 4 an initial global minority of +1 nodes is sufficient to quickly steer the entire system toward consensus on +1.

We then investigate whether such initial conditions can be determined explicitly for a given large random regular graph. To this end, we introduce a new algorithm, which we name history-passing reinforcement (HPR), designed to find such initial configurations with a minority of +1 nodes. We find, as a main result, that the HPR algorithm finds initial configurations where the minority takes over the majority for d-regular random graphs with d ≥ 4.

The HPR algorithm outperforms standard simulated annealing-based methods, but does not reach the lowest densities predicted by the BDCM. Rather, the lowest density achievable by the algorithm is near the onset of a dynamical one-step replica symmetry breaking (d1RSB) phase, which we estimate using a one-step replica symmetry breaking (1RSB) formulation of the BDCM. While we focus on the majority dynamics and random d-regular graphs, the algorithm can be extended to other dynamical rules and classes of sparse graphs.

The analytical study of non-equilibrium properties of dynamical systems is notoriously hard. The backtracking dynamical cavity method (BDCM) is a step forward in understanding such systems by characterizing the properties of attractors on large sparse graphs. In particular, it has allowed us to study majority dynamics, answering questions such as “What is the minimal initial number of +1 nodes needed to end up in a +1 global consensus?”. In this thesis, we solve the BDCM equations iteratively on full instances of random regular and Erdős–Rényi graphs, which gives us lower bounds on the minimal fraction of initial +1 nodes necessary for consensus. Furthermore, we aim to find these initial conditions. To this end, we introduce a novel algorithm that we coin history passing reinforcement (HPR). It is an adaptation of the belief propagation reinforcement algorithm to the BDCM framework. We find that our algorithm outperforms standard Monte Carlo based methods, and comes close to the theoretical limits predicted by BDCM. Notably, we find initial conditions where the final consensus is the original opinion of the minority. While we implement HPR in the setting of majority dynamics on random regular graphs, the algorithm generalizes naturally to broader classes of dynamics and network topologies. Finally, we explore the implications of one-step replica symmetry breaking (1RSB) for the algorithmic performance of HPR. We find that the onset of the dynamical 1RSB phase corresponds to the emergence of an algorithmically hard regime for HPR in this setting.

Thermodynamic uncertainty relations (TURs) interrelate dynamical quantities, like the rate of current and its fluctuations, and the entropy production. They are well established for several thermodynamically consistent time-homogeneous Markov processes such as the overdamped Brownian motion in a tilted periodic potential (TP). However, for processes subjected to time-dependent external driving, the general framework for such relations is unknown. Here we focus on a class of periodically driven systems, whose dynamics can be mapped onto the ones of time-homogeneous Markov processes. We leverage this mapping to derive the entropy production for the overdamped Brownian motion in a travelling-wave potential (TW), which yields an inverse TUR, i.e., the upper bound on the entropy production. This bound is given by the rate of current and the dispersion coefficient, which are experimentally observable quantities. The inverse TUR delivers bounds on kinetic efficiency of a transport of particles by TW potential, such as the recently demonstrated experiments with an optical conveyor belt (OCB). The measured values of the resulting speed of submicrometer-sized colloidal particle, when subjected to transport by OCB moving at certain speeds, match our results. Additionally, using the inverse TUR, we analyse the bounds on thermodynamic cost and precision in stochastic processes. We broaden the results in the case of Brownian clocks by discussing the continuous setting and providing also the upper bound on the product of cost and precision. The precise and dissipationless regime of these clocks is explored. The derived theoretical predictions are tested by Brownian dynamics simulations.