Abstract

Reducing SAT to Max2SAT or MaxCUT makes sense to show that both problems are NP-hard. It also makes sense to define approximation algorithms (although the obtained algorithms are not better than the existing ones). In this talk, we will describe a reduction to Max2XOR with interesting properties to exploit if the original instance has high modularity. I will also present some ideas on how approximate algorithms can be applied to solve Max2XOR and discuss the difficulties in defining a complete proof system for Max2XOR.

Attachment