Raghavendra's famous result from 2008 fully characterizes the inapproximability of every maximum constraint satisfaction problem (Max-CSP). However, the result inherently loses perfect completeness. This means that it does not say anything about the complexity of solving satisfiable Max-CSP instances.
In this talk, I will discuss inapproximability of linear equations over non-abelian groups. We show that even if the instance is satisfiable, it is NP-hard to beat the random assignment algorithm for 'perfect groups'. This is in stark contrast to the problem of solving linear equations over abelian groups, in which case we know how to find a satisfying assignment, if it exists, efficiently. We also give tight inapproximability results for solving linear equations over any non-abelian group.
The proof techniques involve Fourier analysis over non-abelian groups and lots of applications of the Cauchy-Schwarz inequality.
