Campus Event Calendar
Event Entry
What and Who
Expressive Power of Homomorphism Query Algorithms
Arnar Ágúst Kristjánsson
University of Amsterdam
PhD Application Talk
AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 29 January 2025
15:30
30 Minutes
Virtual talk
zoom
Abstract
The left homomorphism profile of a finite relational structure A is a list containing the number of homomorphisms from every finite structure to A. The notion of a homomorphism query algorithm allows us to study the expressive power of homomorphism profiles and compare it with the expressive power of logics or classes of algorithms, whose relation has been studied in descriptive complexity.
A query algorithm consists of a finite tuple of structures F a matching set X of tuples of natural numbers. It accepts the structures whose homomorphism profile, restricted to F, falls into X.
We will explore some of my recent results about the expressive power of variations of homomorphism query algorithms. Among them is the result that for any natural number k there exists a class of digraphs that is not expressible by an adaptive k query algorithm.
We explore directions for future research, one possibility is to allow for an infinite amount of queries in the algorithm. There are indications that the expressive power of such algorithms might relate to the expressive power of fixpoint logics or datalog.
If successful, this research would extend the relation between logic and algorithms to also include query algorithms, offering potential new insights into long-standing problems in complexity theory.
A query algorithm consists of a finite tuple of structures F a matching set X of tuples of natural numbers. It accepts the structures whose homomorphism profile, restricted to F, falls into X.
We will explore some of my recent results about the expressive power of variations of homomorphism query algorithms. Among them is the result that for any natural number k there exists a class of digraphs that is not expressible by an adaptive k query algorithm.
We explore directions for future research, one possibility is to allow for an infinite amount of queries in the algorithm. There are indications that the expressive power of such algorithms might relate to the expressive power of fixpoint logics or datalog.
If successful, this research would extend the relation between logic and algorithms to also include query algorithms, offering potential new insights into long-standing problems in complexity theory.
Contact
Ina Geisler
+49 681 9325 1802
--email hidden
Virtual Meeting Details
Zoom
passcode not visible
logged in users only
Ina Geisler, 01/24/2025 12:43 -- Created document.