2015/05/13 by Boaz Barak, Barak, Boaz, Ankur Moitra +17 · 3 citations
Computer Science · Engineering · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1505.03424
openalex publication_date 2015/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for any odd k and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a (1)/(2) + Ω(1/√(D)) fraction of constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a (1)/(2) + Ω(D-3/4) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a μ+ Ω(1/√(D)) fraction of constraints, where μ is the fraction that would be satisfied by a uniformly random assignment.