A recent line of work studies language generation in the limit, a formal model of language learning where an algorithm observes an adversarially generated enumeration of strings from an unknown target language $K$ and must eventually generate new, unseen strings from $K$. In this model, Kleinberg and Mullainathan (2024) proved that generation is achievable in surprisingly general settings; whenever $K$ belongs to a known countable collection of languages. However, their generator, while quite general, suffers from “mode collapse:” it generates from an ever-smaller subset of the target. To address this, Kleinberg and Wei (2025a) introduced a stronger notion of dense generation, requiring the output to asymptotically cover a positive fraction of the target, and showed it remains achievable for all countable collections. Both of these works rely on the crucial assumption of \textit{perfect} data: the adversary can neither insert strings from outside the target language (i.e., noise) nor omit strings from it (i.e., omissions). In practice, training data for language models is notoriously noisy, raising the fundamental question: \begin{center} \emph{How much contamination (either omissions or insertions) can language generation tolerate?} \end{center} Recent works have made partial progress on this question by studying (non-dense) generation with either finite amounts of noise (but no omissions) (Raman and Raman, 2025) or omissions (but no noise) (Bai et al., 2026). We characterize the contamination tolerance of both types of generation by proving the following results: \begin{itemize} \item \textbf{Generation under Contamination:} Language generation in the limit is achievable for all countable collections if and only if the fraction of contaminated examples converges to zero. When this condition fails, we characterize the collections which remain generable. \item \textbf{Dense Generation under Contamination:} Dense generation is achievable for all countable collections if and only if the amount of contamination is finite. For an infinite amount of contamination, we provide several characterizations of when dense generation is possible, showing it is strictly less robust than standard generation. \end{itemize} As a byproduct, we also resolve an open question of (Raman and Raman, 2025) on generation with membership oracle access under finite contamination.

We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan (2024), under the constraint of differential privacy. We consider the \emph{continual release} model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an $\varepsilon$-differentially-private algorithm that generates in the limit from \emph{any} countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size $k$ for which uniform private generation requires $\Omega(k/\varepsilon)$ samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language \emph{identification} in the limit. Here, we show that privacy creates fundamental barriers. We prove that no $\varepsilon$-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the \emph{stochastic} setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.

Recent works in average-case complexity have identified stable (noise-stable) algorithms as a central class. Specifically, in average-case optimization, the class is conjectured to capture the power of polynomial-time computation for many problems. This perspective has been supported by establishing variants of the Overlap Gap Property (OGP) phase transitions just below conjectured polynomial-time thresholds. Yet, it was recently challenged by Schramm and Li (2025), who showed that Shortest Path in random graphs exhibits the OGP—and hence all stable algorithms fail—despite being solvable in polynomial time. This counterexample has also been particularly curious as it appeared rather distinct from other classical “noiseless" counterexamples, such as solving random linear systems. By contrast, the power of stable methods in statistical estimation has remained unclear. A central difficulty is the absence of an OGP-type phenomenon that can uniformly exclude all stable methods. Instead, existing lower bounds largely focus on the related class of low-degree polynomials and are confined to restricted models, such as Gaussian additive models, reflecting the high technical difficulty of controlling the minimum mean-squared error (MMSE) of low-degree estimators. In this work, we show that for all statistical estimation problems, a natural MMSE instability (discontinuity) condition implies the failure of stable algorithms, serving as a version of OGP for estimation tasks. Using this criterion, we establish separations between stable and polynomial-time algorithms for the following MMSE-unstable tasks (i) Planted Shortest Path, where Dijkstra’s algorithm succeeds, (ii) random Parity Codes, where Gaussian elimination succeeds, and (iii) Gaussian Subset Sum, where lattice-based methods succeed. For all three, we further show that all low-degree polynomials are stable, yielding separations against low-degree methods and a new method to bound the low-degree MMSE. In particular, our technique highlights that MMSE instability is a common feature for Shortest Path and the noiseless Parity Codes and Gaussian subset sum. Last, we highlight that our work places rigorous algorithmic footing on the long-standing physics belief that first-order phase transitions—which in this setting translates to MMSE instability—impose fundamental limits on classes of efficient algorithms.

We prove that whenever $p=\Omega(1)$ and for any graph $H$, counting $O(1)$-stars is optimal among all constant degree polynomial tests in terms of strongly separating an instance of $G(n,p),$ from the union of a random copy of $H$ with an instance of $G(n,p).$ Our work generalizes and extends multiple previous results on the inference abilities of $O(1)$-degree polynomials in the literature.

We introduce a new conjecture on the computational hardness of detecting random lifts of graphs: we claim that there is no polynomial-time algorithm that can distinguish between a large random$d$-regular graph and a large random lift of a Ramanujan$d$-regular base graph (provided the lift is corrupted by a small amount of extra noise), and likewise for bipartite random graphs and lifts of bipartite Ramanujan graphs. We give evidence for this conjecture by proving lower bounds against the local statistics hierarchy of hypothesis testing semidefinite programs. We then explore the consequences of the conjecture for the hardness of certifying bounds on numerous functions of random regular graphs, expanding on a direction initiated by Bandeira, Banks, Kunisky, Moore, and Wein (2021). Conditional on this conjecture, we show that no polynomial-time algorithm can certify tight bounds on the maximum cut or maximum independent set of random 3- or 4-regular graphs, or on the chromatic number of random 7-regular graphs. Asymptotically for large degree for the maximum independent set and for any degree for the minimum dominating set, we show similar gaps, finding that naive spectral and combinatorial bounds are optimal among efficiently computable ones. Likewise, for small set vertex and edge expansion in the limit of very small sets, we show that the spectral bounds due to Kahale (1995) are optimal efficient certificates.

We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number $p$ of vertices has value at least $Ω(p^{1/3})$. This is in contrast to the widely believed conjecture that the actual clique number of the Paley graph is $O(\mathrm{polylog}(p))$. Our result may be viewed as a derandomization of that of Deshpande and Montanari (2015), who showed the same lower bound (up to $\mathrm{polylog}(p)$ terms) with high probability for the Erdős-Rényi random graph on $p$ vertices, whose clique number is with high probability $O(\log(p))$. We also show that our lower bound is optimal for the Feige-Krauthgamer construction of pseudomoments, derandomizing an argument of Kelner. Finally, we present numerical experiments indicating that the value of the degree 4 SOS relaxation of the Paley graph may scale as $O(p^{1/2 - ε})$ for some $ε> 0$, and give a matrix norm calculation indicating that the pseudocalibration proof strategy for SOS lower bounds for random graphs will not immediately transfer to the Paley graph. Taken together, our results suggest that degree 4 SOS may break the "$\sqrt{p}$ barrier" for upper bounds on the clique number of Paley graphs, but prove that it can at best improve the exponent from $1/2$ to $1/3$.