Counting on Nowhere Dense Classes

For every effectively nowhere dense class $\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\mathcal{A} \in \mathcal{C}$ and a first-order formula $ϕ(x_1, \dots, x_k, y_1, \dots, y_\ell)$. After the preprocessing,