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.
This is joint work with Subhash Khot.