In gossip networks, a source node forwards time-stamped updates to a network of observers according to a Poisson process. The observers then update each other on this information according to Poisson processes as well. The Age of Information (AoI) of a given node is the difference between the current time and the most recent time-stamp of source information that the node has received. We provide a method for evaluating the AoI of a node in terms of first passage percolation. We then use this distributional identity to prove matching upper and lower bounds on the AoI in terms of connectivity properties of the underlying network. In particular, if one setsXvto be the AoI of nodevon a finite graphGwithnnodes, then we definem*= min{m:m· |Bm(v)| ≥n} whereBm(v) is the ball of radiusminG. In the case when the maximum degree ofGis bounded by Δ we prove EXv= ΘΔ(m*). As corollaries, we solve multiple open problems in the literature such as showing the age of information on a subset of Zdis Θ(n1/(d+1)). We also demonstrate examples of graphs with AoI scaling likenαfor each α ∈ (0, 1/2). These graphs are not vertex-transitive and in fact we show that if one considers the AoI on a graph coming from a vertex-transitive infinite graph then either EXv= Θ(n1/k) for some integerk≥ 2 or EXv=no(1).

Let G be a graph on n vertices of maximum degree $\Delta$. We show that, for any $\delta\gt0$, the down-up walk on independent sets of size $k \leq(1-\delta) \alpha_{c}(\Delta) n$ mixes in time $O_{\Delta, \delta}(k \log n)$, thereby resolving a conjecture of Davies and Perkins in an optimal form. Here, $\alpha_{c}(\Delta) n$ is the NP-hardness threshold for the problem of counting independent sets of a given size in a graph on n vertices of maximum degree $\Delta$. Our mixing time has optimal dependence on $k, n$ for the entire range of k; previously, even polynomial mixing was not known. In fact, for $k=\Omega_{\Delta}(n)$ in this range, we establish a log-Sobolev inequality with optimal constant $\Omega_{\Delta, \delta}(1 / n)$.At the heart of our proof are three new ingredients, which may be of independent interest. The first is a method for lifting $\ell_{\infty}$-independence from a suitable distribution on the discrete cube—in this case, the hard-core model—to the slice by proving stability of an Edgeworth expansion using a multivariate zero-free region for the base distribution. The second is a generalization of the Lee-Yau induction to prove log-Sobolev inequalities for distributions on the slice with considerably less symmetry than the uniform distribution. The third is a sharp decomposition-type result which provides a lossless comparison between the Dirichlet form of the original Markov chain and that of the so-called projected chain in the presence of a contractive coupling.

Designing infinite impulse response filters to match an arbitrary magnitude response requires specialized techniques. Methods like modified Yule-Walker are relatively efficient, but may not be sufficiently accurate in matching high order responses. On the other hand, iterative optimization techniques often enable superior performance, but come at the cost of longer run-times and are sensitive to initial conditions, requiring manual tuning. In this work, we address some of these limitations by learning a direct mapping from the target magnitude response to the filter coefficient space with a neural network trained on millions of random filters. We demonstrate our approach enables both fast and accurate estimation of filter coefficients given a desired response. We investigate training with different families of random filters, and find training with a variety of filter families enables better generalization when estimating real-world filters, using head-related transfer functions and guitar cabinets as case studies. We compare our method against existing methods including modified Yule-Walker and gradient descent and show our approach is, on average, both faster and more accurate.