Relative Complexity of Random Walks in Random Scenery in the absence of a weak invariance principle for the local times

We answer the question of Aaronson about the relative complexity of Random Walks in Random Sceneries driven by either aperiodic two dimensional random walks, two-dimensional Simple Random walk, or by aperiodic random walks in the domain of attraction of the Cauchy distribution. A key step is proving that the range of the random walk satisfies the F\"olner property almost surely.
Comment: 19 pages