An emerging trend in approximate counting is to show that certain `low-temperature problems are easy on typical instances, despite worst-case hardness results. For the class of regular graphs one usually shows that expansion can be exploited algorithmically, and since random regular graphs are good expanders with high probability the problem is typically tractable. Inspired by approaches used in subexponential-time algorithms for Unique Games, we develop an approximation algorithm for the partition function of the ferromagnetic Potts model on graphs with a small-set expansion condition. In such graphs it may not suffice to explore the state space of the model close to ground states, and a novel feature of our method is to efficiently find a larger set of `pseudo-ground states such that it is enough to explore the model around each pseudo-ground state.

We give a new presentation of the main result of Arunachalam, Briët and Palazuelos (SICOMP 2019) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson--Ambainis (AA) conjecture (Theory of Computing 2014), but has the same implications for classical simulation of quantum query algorithms.

We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials. This implies that if the output of $d$-query quantum algorithm is a homogeneous polynomial~$p$ of degree $2d$, then it has a variable with influence at least $[p]^2$.

In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC 2022 and QIP 2023) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.