Factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in which constraints. Thus, an instance of a CSP is completely defined by its factor graph and the list of predicates. We show inapproximability of Max-3-LIN over non-abelian groups (both in the perfect completeness case and in the imperfect completeness case), with the same inapproximability factor as in the general case, even when the factor graph is fixed. Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form x * y * z = g, where x, y, z are the variables and g is a group element. We use representation theory and Fourier analysis over non-abelian groups to analyze the reductions.

翻译：对n变量和m限制的制约性满意度问题实例的系数图是[m]和[n]之间的双边图,其中描述了在哪些变量中出现制约性因素。因此,CSP的例子完全由其系数图和上游数据列表来定义。我们显示,Max-3-LIN相对于非糖尿病群体(在完全完整的情况下和不完善的情况下)是不可接受的,与一般情况相同,即使系数图已经固定,也是不协调的。此外,我们还表明,即使我们将最大-3-LIN中最大-3-LIN中线性方程限制在x * y * z = g,其中x,y,z是变量和g是组元素。我们用代表理论和对非糖尿病群体的四倍分析来分析减少值。