Satisfaction (PACS 2024)
Date: July 7, 2024
Location: Tallinn, Estonia
================================================================================
Workshop Announcement:
Many fundamental computational problems, ranging from Boolean
satisfiability and systems of equations to graph coloring and
homomorphism, can be formulated as satisfying a collection of
constraints on a shared set of variables, and can be modeled as
constraint satisfaction problems (CSPs). The two standard ways of
studying CSPs are structural and semantic restrictions. In the first
case, one restricts interactions between the variables and the
constraints (e.g., by bounding the treewidth of an associated graph)
and studies the parameterized complexity of the problem. In the second
line, one restricts the expressive power of the constraints and mainly
studies polynomial-time complexity using methods from universal
algebra, model theory, and logic.
The goal of the workshop is to bring together these two research
communities to facilitate an exchange of ideas and tools.
The workshop is motivated by a series of exciting recent developments
in the intersection of parameterized complexity and constraint
satisfaction. In light of recent progress in parameterized complexity
theory, new connections between graph width parameters, complexity
classes, and the CSP have been discovered. Algorithmic breakthroughs
in graph separation and transversal problems have reinvigorated the
study of CSP parameterized by the solution cost. In a related
development, reductions into CSP with few variables have been
successfully applied in resolving open problems, and a new width
parameter for graphs and matrices called twinwidth was employed in
dealing with the resulting CSPs.
The workshop will include two tutorials: one on the algebraic approach
to CSPs and another on the parameterized complexity toolbox for CSPs.
These will be followed by invited survey talks on the topics including
* CSP parameterized by the solution cost,
* graph homomorphisms,
* kernelization & sparsification, and
* structural restrictions to CSPs.
We also plan to have an open problem session.
Confirmed invited speakers:
- Andrei Krokhin, Durham University, UK
- Dániel Marx, CISPA Helmholz Center for Information Security,
Saarbrücken, Germany
- Marcin Pilipczuk, University of Warsaw, Poland
- Paweł Rzążewski, Warsaw University of Technology, Poland
- Magnus Wahlström, Royal Holloway University of London, UK
- Standa Živný, Oxford University, UK
================================================================================
Registration of Interest:
We cordially invite you to attend the workshop (all presentations are
by invitation). The official registration will be available at the
LiCS/ICALP website. Please also register your interest through this
form: https://forms.gle/o9DFTs563e3qiyJCA
PACS 2024 website: https://pacs2024.github.io/
LiCS/ICALP 2024: https://compose.ioc.ee/icalp2024/
================================================================================
Organizers:
- Dániel Marx, CISPA Helmholz Center for Information Security,
Saarbrücken, Germany
- George Osipov, Linköping University, Sweden
- Roohani Sharma, Max-Plack Institute for Informatics, Saarbrücken, Germany
- Magnus Wahlström, Royal Holloway University of London, UK
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
