Dynamical Mean Field Theory (DMFT) provides an asymptotic description of the dynamics of macroscopic observables in certain disordered systems. Originally pioneered in the context of spin glasses, it has since been used to derive asymptotic dynamical equations for a wide range of models in physics, high-dimensional statistics and machine learning. One of the main tools used by physicists to obtain these equations is the dynamical cavity method, which has remained largely non-rigorous. In contrast, existing mathematical formalizations have relied on alternative approaches, including Gaussian conditioning, large deviations over paths, or Fourier analysis. In this work, we formalize the dynamical cavity method and use it to give a new proof of the DMFT equations for General First Order Methods, a broad class of dynamics encompassing algorithms such as Gradient Descent and Approximate Message Passing.

Given an arbitrary subgraph $H=H_n$ and $p=p_n\in(0,1)$, the planted subgraph model is defined as follows. A statistician observes the union of the "signal," which is a random "planted" copy $H^*$ of $H$, together with random "noise" in the form of an instance of an Erd{ö}s-R{é}nyi graph $G(n,p)$. The goal then of the statistician is to recover the planted $H^*$ from the observed graph. Our focus in this work is to understand the minimum mean-squared error (MMSE) in terms of recovering the edges of $H^*$, as a function of $p$ and $H$. A recent paper [MNSSZ23] characterizes the graphs for which this MMSE curve undergoes a sharp phase transition from $0$ to $1$ as $p$ increases, a behavior known as the All-or-Nothing phenomenon, up to a mild density assumption on $H$. However, their techniques fail to describe the MMSE curves for graphs that do not display such a sharp phase transition. In this paper, we provide a formula for the limiting MMSE curve for any graph $H=H_n$, up to the same mild density assumption. This curve is expressed in terms of a variational formula over pairs of subgraphs of $H$, and is inspired by the celebrated subgraph expectation thresholds from probabilistic combinatorics [KK07]. Furthermore, we give a polynomial-time description of the optimizers of this variational problem. This allows one to efficiently compute the MMSE curve for any given dense graph $H$. The proof relies on a novel graph decomposition as well as a min-max duality theorem which may be of independent interest. Our results generalize to the setting of planting arbitrary monotone boolean properties, where the statistician observes the union of a planted minimal element $A\subseteq[N]$ of a monotone property and a random $\mathrm{Ber}(p)^{\otimes N}$ vector. In this setting, we provide a variational formula inspired by the so-called "fractional" expectation threshold [Tal10], again describing the MMSE curve (in this case up to a multiplicative constant).

STOC ’25, Prague, Czechia

We consider the mutual information between a uniformly-random input and the corresponding output through the deletion channel. We prove an upper bound that’s within approximately 0.1 of the best-known lower bounds for all values of the deletion probabilityd, and much closer for small and larged. We give simulation results which suggest that our upper bound is within 0.05 of the exact value for alld, and within 0.01 ford> 0.75. Despite our upper bounds, based on simulations, we conjecture that the mutual information is positive for all deletion probabilities less than 1. Our results imply impossibility results for the (equivalent) problem of compression of i.i.d. sources correlated via the deletion channel, a relevant model for DNA storage.

Given a probability distribution D over the nonnegative integers, a D-repeat channel acts on an input symbol by repeating it a number of times distributed as D. For example, the binary deletion channel (D=Bernoulli) and the Poisson repeat channel (D=Poisson) are special cases. We say a D-repeat channel is square-integrable if D has finite first and second moments. In this paper, we construct explicit codes for all square-integrable D-repeat channels with rate arbitrarily close to the capacity, that are encodable and decodable in linear and quasi-linear time, respectively. We also consider possible extensions to the repeat channel model, and illustrate how our construction can be extended to an even broader class of channels capturing insertions, deletions, and substitutions.Our work offers an alternative, simplified, and more general construction to the recent work of Rubinstein [3], who attains similar results to ours in the cases of the deletion channel and the Poisson repeat channel. It also slightly improves the runtime and decoding failure probability of the polar codes constructions of Tal et al. [1] and of Pfister and Tal [2] for the deletion channel and certain insertion/deletion/substitution channels. Our techniques follow closely the approaches of Guruswami and Li [4] and Con and Shpilka [5]; what sets apart our work is that to obtain our result, we show that a capacity-achieving code for the channels in question can be assumed to have an "approximate balance" in the frequency of zeros and ones of all sufficiently long substrings of all codewords. This allows us to attain near-capacity-achieving codes in a general setting. We consider this "approximate balance" result to be of independent interest, as it can be cast in much greater generality than just repeat channels.A full version of this paper is available at https://arxiv.org/abs/2201.12746.

We consider the bilateral trade problem, in which two agents trade a single indivisible item. It is known that the only dominant-strategy truthful mechanism is the fixed-price mechanism: given commonly known distributions of the buyer's value B and the seller's value S, a price p is offered to both agents and trade occurs if S ≤ p ≤ B. The objective is to maximize either expected welfare or expected gains from trade . We improve the approximation ratios for several welfare maximization variants of this problem. When the agents' distributions are identical, we show that the optimal approximation ratio for welfare is . With just one prior sample from the common distribution, we show that a 3/4-approximation to welfare is achievable. When agents' distributions are not required to be identical, we show that a previously best-known (1–1/e)-approximation can be strictly improved, but 1–1/e is optimal if only the seller's distribution is known.