Lower Bounds of Functions on Finite Abelian Groups

The problem of computing the optimum of functions on finite abelian groups is an important problem in mathematics and computer science. Many combinatorial problems, such as MAX-SAT, MAX-CUT and the knapsack problem, can be recognized as optimization problems on the group \(C_2^n = \{-1,1\}^n\) . This paper proposes an algorithm that efficiently computes verifiable lower bounds of functions on finite abelian groups by the technique of the Fourier sum of squares with error. Moreover, we propose a new rounding method to obtain a feasible solution that minimizes the objective function as much as possible. We also implement the algorithm and test it on MAX-SAT benchmark problems and random functions. These experiments demonstrate the advantage of our algorithm over previously known methods.