Behrisch, M. (2023, February 22). Algebraic theory for the fine-grained analysis of constraint satisfaction type problems [Presentation]. Seminario de Matemáticas del ITAM, Ciudad de México, Mexico.
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
Research Areas:
Computer Science Foundations: 40% Fundamental Mathematics Research: 60%