Behrisch, Mike

2025-04-07T10:02:14Z

2025-04-07T10:02:14Z

2025-02-26

<div class="csl-bib-body"> <div class="csl-entry">Behrisch, M. (2025, February 26). <i>Weak bases for relational clones and their uses</i> [Presentation]. Seminario Tardes de Café y Álgebra, UAM-I, Ciudad de México, Mexico.</div> </div>

http://hdl.handle.net/20.500.12708/213727

A weak base of a relational clone 𝑄 on a finite set is a finite generating system 𝑊 ⊆ 𝑄 of 𝑄 = [𝑊]∃∧= under primitive positive definability that generates the smallest weak system 𝑆_𝑄 = [𝑊]∧= among all weak systems 𝑆 with equality having the same polymorphisms as 𝑄. Many computational problems in theoretical computer science are parametrised by finite sets of relations, for example, constraint satisfaction problems, or they can be rephrased in that form. The relative difficulty of such computational problems is compared using an appropriate notion of reduction for the type of problem (e.g., decision, counting, optimisation, approximation problem etc.). If 𝑅, 𝑅' are finite parameter sets of relations, then expressibility relationships of the form 𝑅 ⊆ [𝑅'] typically lead to reductions 𝖯(𝑅) ≤ 𝖯(𝑅') among the parametrised problems. Here [ ] denotes a closure operator on finitary relations that is appropriate for the type of problem 𝖯 and the sort of reduction ≤ under consideration. The most basic closure that works for many problems and reductions is expressibility by conjunctive formulæ [ ]∧; a familiar expressibility notion that works for constraint satisfaction decision problems (but not in every other case) is primitive positive closure [ ]∃∧=. Weak bases can help to reduce the effort of obtaining sufficiently many reductions in complexity classifications by lowering the strength of the closure operator [ ] for which one needs to show that 𝑅 ⊆ [𝑅'] implies 𝖯(𝑅) ≤ 𝖯(𝑅'): namely, the conjunctive equality closure [ ] = [ ]∧= suffices for arbitrary weak bases, and the even weaker conjunctive closure [ ] = [ ]∧ suffices for weak bases consisting of irredundant proper relations. In the context of complexity classifications, weak bases with irredundant proper relations can thus be used to identify weakest hard problems. In the talk we shall review some details of how this works, look at concrete families of weak bases, consider problems where this approach has been successfully applied in the past, and discuss some recent results about weak bases, as well as some prospects for future investigation.

en

weak base

relational clone

strong partial clone

fine grained complexity

Weak bases for relational clones and their uses

Presentation

Vortrag

Presentation

invited

I1

C5

Logic and Computation

Computer Science Foundations

60

40

https://www.youtube.com/live/xrxhwh1XYmY

E104-01 - Forschungsbereich Algebra

E104 - Institut für Diskrete Mathematik und Geometrie

0000-0003-0050-8085

Seminario Tardes de Café y Álgebra, UAM-I

26-02-2025

26-02-2025

Hybrid

Event for scientific audience

Ciudad de México

MX

Universidad Autónoma Metropolitana (UAM), Unidad Iztapalapa

Behrisch, Mike

Informatik

Mathematik

1020

1010

40

60

en

conference presentation

none

no Fulltext

Publications

http://purl.org/coar/resource_type/R60J-J5BD

E104-01 - Forschungsbereich Algebra

0000-0003-0050-8085

E104 - Institut für Diskrete Mathematik und Geometrie