License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.2
URN: urn:nbn:de:0030-drops-140717
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14071/
Bulatov, Andrei A.
Symmetries and Complexity (Invited Talk)
Abstract
The Constraint Satisfaction Problem (CSP) and a number of problems related to it have seen major advances during the past three decades. In many cases the leading driving force that made these advances possible has been the so-called algebraic approach that uses symmetries of constraint problems and tools from algebra to determine the complexity of problems and design solution algorithms. In this presentation we give a high level overview of the main ideas behind the algebraic approach illustrated by examples ranging from the regular CSP, to counting problems, to optimization and promise problems, to graph isomorphism.
BibTeX - Entry
@InProceedings{bulatov:LIPIcs.ICALP.2021.2,
author = {Bulatov, Andrei A.},
title = {{Symmetries and Complexity}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {2:1--2:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14071},
URN = {urn:nbn:de:0030-drops-140717},
doi = {10.4230/LIPIcs.ICALP.2021.2},
annote = {Keywords: constraint problems, algebraic approach, dichotomy theorems}
}
|
Keywords: |
|
constraint problems, algebraic approach, dichotomy theorems |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
