We design the first fully polynomial-time randomized approximation scheme ($\mathsf{FPRAS}$) for approximately counting and uniformly sampling common bases of two matroids given by their independence oracles. Moreover, our algorithms generalize far beyond this to Hadamard products of two probability measures on the Boolean cube satisfying a simple nonnegative curvature condition. These algorithmic primitives have myriad applications in statistical physics, polyhedral combinatorics, the theory of quantum many-body systems, and beyond. The central difficulty is that the hard constraints imposed by the two input matroids (or the two input measures, more generally) obstruct traditional approaches based on local Markov chains. Relaxing these constraints can restore rapid mixing, but configurations that satisfy the original hard constraints may become exponentially rare if this is done naïvely. Our main contribution is a novel approach for approximate counting that marries Markov chain Monte Carlo (MCMC) with convex programming to overcome these obstacles: - We relax the intersection by imposing an overlap penalty on the product measure formed by the two input measures. We prove, via an integrated Bochner-type method, that this "soft intersection" satisfies a Poincaré Inequality uniformly over all external fields. - We use samples from the relaxed distribution to solve a dual maximum entropy convex program inspired by the Gurvits capacity. This program reweights the soft intersection measure using external fields to boost the aggregate probability of configurations satisfying the hard intersection constraint, without changing their relative weights. We bound the success probability directly using the uniform Poincaré Inequality and smallness of the gradient norm. AI Disclosure: GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used to develop the ideas in this paper.
It is proved that, for every $δ\in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q \geq (1+δ)Δ$ and the underlying graph has girth at least $5$ and maximum degree $Δ= Ω_δ(1)$. This result also extends to general multi-spin systems satisfying a $\textit{local spectral contraction}$ condition, including the anti-ferromagnetic Potts model with $q\geq (1+δ)(1-β)Δ$. These results are achieved by a new spectral local-to-global principle on graphs with girth at least five for general multi-spin systems, and a novel Fourier analysis for Glauber dynamics on a star. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra.
We design the first fully polynomial-time randomized approximation scheme ($\mathsf{FPRAS}$) to estimate the mixed volume of $n$ arbitrary compact convex sets in $\mathbb{R}^{n}$ specified by weak membership oracles. This disproves a longstanding conjecture of Gurvits (2009). $\textbf{AI Disclosure}$ The main ideas were generated entirely by GPT 6 Astra. The purpose of this paper is to provide a human-written exposition of the algorithm.
We give the first polynomial-time algorithm to estimate the partition function of the antiferromagnetic Ising model on the uniformly random $d$-regular graph to arbitrarily high accuracy for all inverse temperatures up to the Kesten-Stigum threshold. This is the entire regime in which the model is "replica symmetric," and is conjectured to be optimal for polynomial-time counting and sampling. To achieve our algorithmic result, we establish the absence of Fisher zeros for the partition function in a constant-width strip around the interval from $0$ up to the Kesten-Stigum threshold, with high probability over the randomness of the input graph. AI Disclosure: The overarching vision and proof architecture were developed solely by the authors without AI input. GPT 5.5 Pro was used, with extensive guidance from the authors, for only a few minor technical aspects of the proof. The authors independently verified correctness and wrote everything by hand. We take full responsibility for its contents. A more detailed statement can be found in Section 1.2.