## 2024 Lindström Lectures: Phokion G. Kolaitis

published: 2024-02-21

event dates:
2024-04-15
–
2024-04-17

On 15–17 April, 2024 the University of Gothenburg will host the 2024 edition of
its annual Lindström Lectures. The Lindström Lectures is a distinguished lecture
series initiated in 2013 celebrating the memory of Per (Pelle) Lindström, former
(and first) professor in logic at the University of Gothenburg. For information
about the Lindström lecture series see:

https://www.gu.se/en/flov/the-lindstrom-lectures

We are proud to announce that the 2024 Lindström Lectures will be delivered by
**Phokion G. Kolaitis**, Distinguished Research Professor at UC Santa Cruz and a
Principal Research Staff Member at the IBM Almaden Research Center, US.
Professor Kolaitis will deliver a **public lecture on Monday, 15 April 2024,
1800–2000** and a **research lecture on Wednesday, 17 April at 10–12**. Both
lectures will be held in the Faculty of Humanities, University of Gothenburg.
The public lecture will also be broadcast over Zoom. A Zoom link for the event
will be distributed on the
Nordic Online Logic Seminar
mailing list.

## Public Lindström Lecture

**Monday, 15 April 2024 at 18:00 (UTC+2)** at the Faculty of Humanities,
University of Gothenburg and over Zoom

**Phokion G. Kolaitis** (University of California Santa Cruz and IBM Research)

*Characterizing Rule-based Languages*

Abstract: There is a mature body of work in logic aiming to characterize logical
formalisms in terms of their structural or model-theoretic properties. The
origins of this work can be traced to Alfred Tarski’s program to characterize
metamathematical notions in “purely mathematical terms” and to Per Lindström’s
abstract characterizations of first-order logic. For the past forty years,
rule-based logical languages have been widely used in databases and in related
areas of computer science to express integrity constraints and to specify
transformations in data management tasks, such as data exchange and
ontology-based data access. The aim of this talk is to present an overview of
more recent results that characterize various classes of rule-based logical
languages in terms of their structural or model-theoretic properties.

## Research Lindström Lecture

**Wednesday, 17 April 2024 at 10:00 (UTC+2)**

**Phokion G. Kolaitis** (University of California Santa Cruz and IBM Research)

*Homomorphism Counts: Expressive Power and Query Algorithms*

Abstract: A classical result by Lovász asserts that two graphs G and H are
isomorphic if and only if they have the same left profile, that is, for every
graph F, the number of homomorphisms from F to G coincides with the number of
homomorphisms from F to H. A similar result is also known to hold for right
profiles, that is, two graphs G and H are isomorphic if and only if for every
graph F, the number of homomorphisms from G to F coincides with the number of
homomorphisms from H to F. During the past several years, there has been a study
of equivalence relations that are relaxations of isomorphism obtained by
restricting the left profile or the right profile to suitably restricted classes
of graphs, instead of the class of all graphs. Furthermore, a notion of a query
algorithm based on homomorphism counts was recently introduced and investigated.
The aim of this talk is to present an overview of some of the main results in
this area with emphasis on the differences between left homomorphism counts and
right homomorphism counts.