On hardness of some Boolean counting CSPs

Behrisch, Mike; Hermann, Miki

doi:10.34726/5452

Record link:

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

Title:

On hardness of some Boolean counting CSPs

Citation:

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

Publication Type:

Presentation - Conference Presentation

Language:

English

Authors:

Behrisch, Mike
Hermann, Miki

Organisational Unit:

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

Date (published):

4-Jun-2021

Event name:

AAA 101 - 101st Workshop on General Algebra

Event date:

4-Jun-2021 - 6-Jun-2021

Event place:

Novi Sad, Serbia

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 (external):

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

Research Areas:

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

Science Branch:

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

License:

CC BY-NC-ND 4.0