Title: Group representations that resist worst-case sampling,
Abstract: Motivated by expansion in Cayley graphs, we show that there exist infinitely
many groups $G$ with a nontrivial irreducible unitary representation whose
average over every set of $o(\log\log|G|)$ elements of $G$ has operator norm $1
- o(1)$. This answers a question of Lovett, Moore, and Russell, and strengthens
their negative answer to a question of Wigderson.
The construction is the affine group of $\mathbb{F}_p$ and uses the fact that
for every $A \subset \mathbb{F}_p\setminus\{0\}$, there is a set of size
$\exp(\exp(O(|A|)))$ that is almost invariant under both additive and
multiplicatpive translations by elements of $A$.