This Wednesday February 22nd., we have a special session of our Mathematics Seminar, which this week will be in addition of the usual talk on Friday.

On this occasion the speaker is Mike Behrisch, from the Institute for Discrete Mathematics and Geometry, Technische Universität Wien.

Here is the title and abstract of his talk:

Title:

Algebraic theory for the fine-grained analysis of constraint

satisfaction type problems



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.

----------------------------------

Esperamos que puedan asistir a esta plática que se llevará a cabo en el salón B3, de 3:00 a 4:00 PM del miércoles 22 de febrero.

We hope to see you all at Rm. B3, from 3:00 to 4:00 PM, on Wednesday February 22nd.