Approximation Algorithms for Noncommutative CSPs

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

Noncommutative constraint satisfaction problems (CSPs) are higher-dimensional operator extensions of classical CSPs. Their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-3-Cut. We present a 0.864-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and generalized anticommutation, which may be of independent interest.
OriginalsprogEngelsk
TitelIEEE Annual Symposium on Foundations of Computer Science
Publikationsdatookt. 2024
ISBN (Elektronisk)979-8-3315-1674-1
StatusUdgivet - okt. 2024

Citationsformater