Approximation Algorithms for Noncommutative CSPs

Taro Johann Spirig

Approximation Algorithms for Noncommutative CSPs

Department of Mathematical Sciences

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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.

Original language	English
Title of host publication	IEEE Annual Symposium on Foundations of Computer Science
Publication date	Oct 2024
ISBN (Electronic)	979-8-3315-1674-1
Publication status	Published - Oct 2024

Cite this

@inproceedings{c071876b63984730b91c7952d82c0a25,

title = "Approximation Algorithms for Noncommutative CSPs",

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.",

author = "Spirig, {Taro Johann}",

year = "2024",

month = oct,

language = "English",

booktitle = "IEEE Annual Symposium on Foundations of Computer Science",

}

TY - GEN

T1 - Approximation Algorithms for Noncommutative CSPs

AU - Spirig, Taro Johann

PY - 2024/10

Y1 - 2024/10

N2 - 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.

AB - 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.

M3 - Article in proceedings

BT - IEEE Annual Symposium on Foundations of Computer Science

ER -