Dear
all,
this
is a reminder for Martin
Grohe's
talk with
the title "The Complexity of Constraint
Satisfaction" taking
place today
(16.05) at 12:30 in
the B-IT
room 5053.2.
Please find the details
below
--- Abstract
---
The objective of a constraint satisfaction problem (CSP) is to assign values to variables subject to constraints on the values.
Obviously, this is a very general type of problem, and it is not surprising that many algorithmic problems in various application
domains can be described as CSPs. It is neither surprising that, in general, CSPs are computationally hard. Considerable
efforts have been made to precisely understand the complexity of CSPs, with the goal of identifying tractable restrictions and,
ultimately, determining the boundary between tractable and intractable CSPs.
A deep theory based on methods from logic, combinatorics, and universal algebra has evolved around these questions.
In this survey talk, I will give an overview of the main results and techniques of this theory, and I will highlight some
current research topics and open questions.
Part of the programme of the research training group UnRAVeL
is a series of lectures on the topics of UnRAVeL’s research thrusts
algorithms and complexity, verification, logic and languages, and their application scenarios. Each lecture is given by one of the researchers involved in UnRAVeL.
This years topic is
"UnRAVeL - New Ideas!". In
these lectures, UnRAVeL professors will discuss current research as well as highlight open problems and offer a perspective on potential future directions.
All interested doctoral researchers and master students are invited
to attend the UnRAVeL lecture series 2024 and engage in discussions with researchers and doctoral students.
We are looking forward to seeing you at the lectures.
Kind regards,
Jan-Christoph for the organisation committee