Combinatorial Games in Finite Model Theory, 2023

Workshop affiliated with LICS 2023
Boston, USA, 24-25 June 2023

Logistical Note

The workshop has moved to Room B12 (behind the snacks).

Aim

The goal of this workshop is to promote work at the interface of complexity and logic. The workshop has two main foci: the first is recent progress in using combinatorial games to prove logical (in)expressiblity results, the second is limitations in the method of combinatorial games as a tool for establishing lower bounds in computational complexity.

Dates (Updated)

Abstract Submission Deadline: Friday May 5
Author Notification: Thursday May 11
Early Bird Registration Deadline: Friday May 12
Regular Registration Deadline Friday June 9
Workshop Dates: June 24th and 25th

Invited Speakers

Schedule

Day One: Saturday, June 24.

8:15 - 9:00AM Light Breakfast
9:30 - 10:30AM One Two Three … Ehrenfeucht: Descriptive Complexity and Games
Neil Immerman (Invited Speaker)
10:30 - 11:00AM Coffee Break
11:00 - 11:35AM Combinatorial Games for Quantifier Number
Rik Sengupta
11:40AM - 12:15PM From Quantifier Depth to Quantifier Number: Separating Structures in Finite Variable Logic
Harry Vinall-Smeeth and Christoph Berkholz
12:15 - 2:30PM Lunch
2:30 - 3:30PM Barriers in Complexity Theory
Antonina Kolokolova (Invited Speaker)
3:30 - 4:00PM Coffee Break
4:00 - 4:35PM Quantifiers Closed Under Partial Polymorphisms
Anuj Dawar and Lauri Hella
4:40 - 5:15PM Flipper Games for Monadically Stable Graph Classes
Wojciech Przybyszewski

Day Two: Sunday, June 25.

8:15 - 9:00AM Light Breakfast
9:30 - 10:30AM On Limitations of the Ehrenfeucht-Fraïssé-method in Descriptive Complexity
Yijia Chen (Invited Speaker)
10:30 - 11:00AM Coffee Break
11:00 - 11:35AM Second-Order Quantifiers with Poly-Logarithmic Bounds
Shiguang Feng, Kexu Wang, and Xishun Zhao
11:40AM - 12:15PM Indistinguishability games for Extensions of PDL with Intersection and Converse
Diego Figueira, Santiago Figueira, and Edwin Pin
12:15 - 2:30PM Lunch
2:30 - 3:30PM Ehrenfeucht-Fraïssé Games for Semiring Semantics
Erich Grädel (Invited Speaker)
3:30 - 4:00PM Coffee Break
4:00 - 5:15PM Open Problem Session

Contributed Talks

Those wishing to speak at the workshop on any topic related to combinatorial games in finite model theory are invited to submit an Extended Abstract of up to three pages (including references) in at least 10pt font via EasyChair at this link, describing the content of the contributed presentation.

At least one author from each accepted abstract must register for the workshop. Presenters at the workshop are expected to be in person.

We encourage the submission of abstracts on work at all levels of progress, including already published results, work in progress, novel contributions, as well as survey-type contributions. Early-stage work connecting this field of study to other fields is also highly encouraged.

Depending on the number of submissions, contributed talks will be 15-30 minutes long. A collection of abstracts of all invited and contributed talks will be posted at the workshop website.

Registration & Local Information

Participation in person is strongly encouraged. However, the LICS 2023 conference also offers a basic virtual attendance option for all the workshops and the main conference (video broacasting + chat for questions) for people that are not presenting and who will not be able to attend in person. Purchase registration here, and for details, see the main LICS Registration Page.

Organising and Program Committee