Let $G$ be a finite group, and let $f_1,f_2$ be two real-valued class functions of $G$. Assume that multiplying elements of $G$ takes $O(1)$-time.
Let $s:G\to \mathbb{R}$ be defined by $$s(g):=\sum_{x\in G} f_1(x)f_2(g\cdot x).$$
When $G$ is abelian, the maximum of $s$ can be found efficiently using FFT and other similar methods.
For most abelian groups, the complexity of finding the maximum of $s$ and the element of $G$ at which the maximum is attained is $$O(|G| \ln |G|).$$
Question 1: Is it true in general that one can beat the naive algorithm of $O(|G|^2)$? What is the most efficient algorithm for a given $G$?
Question 2: Is it necessary to require that $f_1,f_2$ are class functions? For abelian $G$'s, this condition degenerates. For non-abelian $G$'s, if one wants to apply representation theory, this looks like a necessary condition. But maybe there are other lines of attack.
More concretely, are there examples of $G$'s for which one can solve the non-restricted problem in asymptotically less than $O(|G|^2)$ operations?
