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: | |
Author Notification: | |
Early Bird Registration Deadline: | |
Regular Registration Deadline | |
Workshop Dates: | June 24th and 25th |
Invited Speakers
- Yijia Chen (Shanghai Jiao Tong University)
- Erich Grädel (RWTH Aachen)
- Neil Immerman (University of Massachusetts Amherst)
- Antonina Kolokolova (Memorial University of Newfoundland)
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
- Marco L. Carmosino, IBM Research
- Ronald Fagin, IBM Research
- Phokion G. Kolaitis, UC Santa Cruz and IBM Research
- Jonathan Lenchner, IBM Research
- Ryan Williams, MIT