Leslie Ann Goldberg

Andreas Galanis, Leslie Ann Goldberg, Xandru Mifsud

We study random walks on dynamically evolving graphs, where the environment is given by a time-dependent subset of the edges of an underlying graph. Concretely, following the recently introduced framework of Lelli and Stauffer, we consider a random walk interacting with a dynamical random-cluster environment, in which edges are updated with rate $μ>0$ according to Glauber dynamics with parameters $p$ and $q$, and the walker moves at rate 1 but may only traverse edges that are present at the time of the move. This setting introduces strong dependencies between the walk and the environment, as edge-update probabilities depend on the global connectivity structure. We focus on the case where the underlying graph is a random $d$-regular graph and the parameters lie in the subcritical regime $p < p_{\mathrm{u}}(q, d)$ where it is known that the Glauber dynamics mixes quickly. Our main result is to show that for any $\varepsilon >0$ and all $q \ge 1$, for all $p$ in the subcritical regime, the mixing time of the joint process is $Θ(\log n)$ (in continuous time) whenever $μ\geq \varepsilon \log n$. This matches the mixing time of the simple random walk on a static random regular graph, showing that in this regime the evolving environment does not slow down mixing. Our proof is based on a coupling argument that uses path-count techniques to overcome the dependencies in the edge dynamics by controlling the structure of the environment along typical trajectories.

Andreas Galanis, Leslie Ann Goldberg, Xusheng Zhang

Consider a $k$-SAT formula $Φ$ where every variable appears at most $d$ times, and let $σ$ be a satisfying assignment of $Φ$ sampled proportionally to $e^{βm(σ)}$ where $m(σ)$ is the number of variables set to true and $β$ is a real parameter. Given $Φ$ and $σ$, can we learn the value of $β$ efficiently? This problem falls into a recent line of works about single-sample ("one-shot") learning of Markov random fields. The $k$-SAT setting we consider here was recently studied by Galanis, Kandiros, and Kalavasis (SODA'24) where they showed that single-sample learning is possible when roughly $d\leq 2^{k/6.45}$ and impossible when $d\geq (k+1) 2^{k-1}$. Crucially, for their impossibility results they used the existence of unsatisfiable instances which, aside from the gap in $d$, left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold of $k$-SAT formulas of bounded degree. Our main contribution is to answer this question negatively. We show that one-shot learning for $k$-SAT is infeasible well below the satisfiability threshold; in fact, we obtain impossibility results for degrees $d$ as low as $k^2$ when $β$ is sufficiently large, and bootstrap this to small values of $β$ when $d$ scales exponentially with $k$, via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm and obtain significantly stronger bounds on $d$ in terms of $β$. In particular, for the uniform case $β\rightarrow 0$ that has been studied extensively in the sampling literature, our analysis shows that learning is possible under the condition $d\lesssim 2^{k/2}$. This is nearly optimal (up to constant factors) in the sense that it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for $d\gtrsim 2^{k/2}$.