Given a noisy linear measurement $y = Ax + \xi$ of a distribution $p(x)$, and a good approximation to the prior $p(x)$, when can we sample from the posterior $p(x \mid y)$? Posterior sampling provides an accurate and fair framework for tasks such as inpainting, deblurring, and MRI reconstruction, and several heuristics attempt to approximate it. Unfortunately, approximate posterior sampling is computationally intractable in general. To sidestep this hardness, we focus on (local or global) log-concave distributions $p(x)$. In this regime, Langevin dynamics yields posterior samples when the exact scores of $p(x)$ are available, but it is brittle to score--estimation error, requiring an MGF bound (sub‑exponential error). By contrast, in the unconditional setting, diffusion models succeed with only an $L^2$ bound on the score error. We prove that combining diffusion models with an *annealed* variant of Langevin dynamics achieves conditional sampling in polynomial time using merely an $L^4$ bound on the score error.

In streaming PCA, we see a stream of vectors$x_1, \ldots, x_n \in \mathbb{R}^d$and want to estimate the top eigenvector of their covariance matrix. This is easier if the spectral ratio$\boldsymbol{R}=\lambda_{1}/\lambda_{2}$is large. We ask: how large does$\boldsymbol{R}$need to be to solve streaming PCA in$\boldsymbol{\tilde{O}(d)}$space? Existing algorithms require$\boldsymbol{R=\tilde{\Omega}({d})}$. We show: • For all mergeable summaries,$\boldsymbol{R=\tilde{\Omega}(\sqrt{d})}$is necessary. • In the insertion-only model, a variant of Oja's algorithm gets$\boldsymbol{o(1)}$error for$\boldsymbol{R=O(\log n \log d)}$• No algorithm with$\boldsymbol{o(d^{2})}$space gets$\boldsymbol{o(1)}$error for$\boldsymbol{R=O(1)}$. Our analysis is the first application of Oja's algorithm to adversarial streams. It is also the first algorithm for adversarial streaming PCA that is designed for a spectral, rather than Frobenius, bound on the tail; and the bound it needs is exponentially better than is possible by adapting a Frobenius guarantee.

We show that the TFNP problem Ramsey is not black-box reducible to Pigeon, refuting a conjecture of Goldberg and Papadimitriou in the black-box setting. We prove this by giving reductions to Ramsey from a new family of TFNP problems that correspond to generalized versions of the pigeonhole principle, and then proving that these generalized versions cannot be reduced to Pigeon. Formally, we define$t$-PPP as the class of total NP-search problems reducible to finding a$t$-collision in a mapping from$(t-1) N + 1$pigeons to$N$holes. These classes are closely related to multi-collision resistant hash functions in cryptography. We show that the generalized pigeonhole classes form a hierarchy as$t$increases, and also give a natural condition on the parameters$t_{1}, t_{2}$that captures exactly when$t_{1}$-PPP and$t_2$-PPP collapse in the black-box setting. Finally, we prove other inclusion and separation results between these generalized Pigeon problems and other previously studied TFNP subclasses, such as PLS, PPA, and PLC. Our separation results rely on new lower bounds in propositional proof complexity based on pseudoexpectation operators, which may be of independent interest.

Diffusion models are a remarkably effective way of learning and sampling from a distribution $p(x)$. In posterior sampling, one is also given a measurement model $p(y \mid x)$ and a measurement $y$, and would like to sample from $p(x \mid y)$. Posterior sampling is useful for tasks such as inpainting, super-resolution, and MRI reconstruction, so a number of recent works have given algorithms to heuristically approximate it; but none are known to converge to the correct distribution in polynomial time. In this paper we show that posterior sampling is computationally intractable: under the most basic assumption in cryptography—that one-way functions exist—there are instances for which every algorithm takes superpolynomial time, even though unconditional sampling is provably fast. We also show that the exponential-time rejection sampling algorithm is essentially optimal under the stronger plausible assumption that there are one-way functions that take exponential time to invert.

Diffusion models have become the most popular approach to deep generative modeling of images, largely due to their empirical performance and reliability. From a theoretical standpoint, a number of recent works [CCL+23, CCSW22, BBDD24] have studied the iteration complexity of sampling, assuming access to an accurate diffusion model. In this work, we focus on understanding the *sample complexity* of training such a model; how many samples are needed to learn an accurate diffusion model using a sufficiently expressive neural network? Prior work [BMR20] showed bounds polynomial in the dimension, desired Total Variation error, and Wasserstein error. We show an *exponential improvement* in the dependence on Wasserstein error and depth, along with improved dependencies on other relevant parameters.

It is well known [Lovász, 67] that up to isomorphism a graph~$G$ is determined by the homomorphism counts $\hom(F, G)$, i.e., the number of homomorphisms from $F$ to $G$, where $F$ ranges over all graphs. Thus, in principle, we can answer any query concerning $G$ with only accessing the $\hom(\cdot,G)$'s instead of $G$ itself. In this paper, we deal with queries for which there is a hom algorithm, i.e., there are finitely many graphs $F_1, \ldots, F_k$ such that for any graph $G$ whether it is a Yes-instance of the query is already determined by the vector\[\overrightarrow{\hom}_{F_1,\ldots,F_k}(G):= \big(\hom(F_1,G),\ldots,\hom(F_k,G)\big),\]where the graphs $F_1, \ldots, F_k$ only depend on $φ$. We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. On the other hand, queries expressible as a Boolean combination of universal sentences in first-order logic FO have a hom algorithm. Even though it is not easy to find FO definable queries without a hom algorithm, we succeed to show this for the non-existence of an isolated vertex, a property expressible by the FO sentence $\forall x\exists y Exy$, somehow the ``simplest'' graph property not definable by a Boolean combination of universal sentences.These results provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm. For adaptive query algorithms, i.e., algorithms that again access $\overrightarrow{\hom}_{F_1,\ldots,F_k}(G)$ but here $F_{i+1}$ might depend on $\hom(F_1,G),\ldots,\hom(F_i,G)$, we show that three homomorphism counts $\hom(\cdot,G)$ are both sufficient and in general necessary to determine the isomorphism type of $G$.