reposiTUm: On hardness of some Boolean counting CSPs

Datensatz Zitierlink:

http://hdl.handle.net/20.500.12708/193848
https://doi.org/10.34726/5452

Titel:

On hardness of some Boolean counting CSPs

Zitat:

Behrisch, M., & Hermann, M. (2021, June 4). On hardness of some Boolean counting CSPs [Conference Presentation]. AAA 101 - 101st Workshop on General Algebra, Novi Sad, Serbia. https://doi.org/10.34726/5452

reposiTUm-DOI:

10.34726/5452

Publikationstyp:

Vortrag - Konferenz Präsentation

Sprache:

Englisch

Autor_innen:

Behrisch, Mike
Hermann, Miki

Organisationseinheit:

E104-01 - Forschungsbereich Algebra
E104 - Institut für Diskrete Mathematik und Geometrie

Datum (veröffentlicht):

4-Jun-2021

Veranstaltungsname:

AAA 101 - 101st Workshop on General Algebra

Veranstaltungszeitraum:

4-Jun-2021 - 6-Jun-2021

Veranstaltungsort:

Novi Sad, Serbien

Keywords:

counting complexity; #ETH; #CSP; counting problems; weak base; strong partial clone; restriction-closed partial clone; partial polymorphism; reductions

Abstract:

We relate #ETH to the hardness of certain counting CSPs over Boolean constraint languages with the aim of characterising #ETH. For this we rely on the theory of weak bases as established by Schnoor and Schnoor based on the Galois theory for strong partial clones by Romov. Moreover, we exploit and extend results of Lagerkvist describing certain irredundant weak bases in the Boolean case.

Link (extern):

https://aaa101.pmf.uns.ac.rs/

Forschungsschwerpunkte:

Mathematical and Algorithmic Foundations: 40%
Fundamental Mathematics Research: 60%

Wissenschaftszweig:

1020 - Informatik: 40%
1010 - Mathematik: 60%

Lizenz:

CC BY-NC-ND 4.0