<div class="csl-bib-body">
<div class="csl-entry">Behrisch, M. (2023, February 22). <i>Algebraic theory for the fine-grained analysis of constraint satisfaction type problems</i> [Presentation]. Seminario de Matemáticas del ITAM, Ciudad de México, Mexico.</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/158347
-
dc.description.abstract
By a celebrated result of, independently, Bulatov and Zhuk from 2017, the complexity of the fixed parameter constraint satisfaction problem (CSP) over finite domains exhibits a P vs. NP-complete dichotomy under polynomial-time many-one (or even logarithmic space) reductions. This theorem, solving a conjecture that was open for about three decades, is based on a Galois theoretic background theory between functions and relations involving so-called polymorphisms and invariant relations. In the case of related problems as, for example, surjective satisfiability, inverse satisfiability, unique satisfiability, or counting CSPs under parsimonious reductions, one has to take more care with respect to the usable reductions and the algebraic theory becomes more technical. In the talk I will give an introduction to these more fine-grained methods, involving so-called strong partial clones, weak systems and weak bases,
and, if time allows, mention some recent results.
en
dc.language.iso
en
-
dc.subject
constraint satisfaction
en
dc.subject
complexity
en
dc.subject
fine-grained methods
en
dc.subject
strong partial clone
en
dc.subject
weak base
en
dc.subject
weak system
en
dc.title
Algebraic theory for the fine-grained analysis of constraint satisfaction type problems
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.type.category
Presentation
-
tuw.publication.invited
invited
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.id
A3
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.name
Fundamental Mathematics Research
-
tuw.researchTopic.value
40
-
tuw.researchTopic.value
60
-
tuw.publication.orgunit
E104-01 - Forschungsbereich Algebra
-
tuw.author.orcid
0000-0003-0050-8085
-
tuw.event.name
Seminario de Matemáticas del ITAM
es
tuw.event.startdate
22-02-2023
-
tuw.event.enddate
22-02-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Ciudad de México
-
tuw.event.country
MX
-
tuw.event.institution
ITAM
-
tuw.event.presenter
Behrisch, Mike
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
40
-
wb.sciencebranch.value
60
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
item.cerifentitytype
Publications
-
item.openairetype
conference presentation
-
item.openairecristype
http://purl.org/coar/resource_type/R60J-J5BD
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E104-01 - Forschungsbereich Algebra
-
crisitem.author.orcid
0000-0003-0050-8085
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
