Logic and Computational Complexity


NII Shonan Meeting Seminar 096


Yijia Chen (Fudan University, China)

Rodney Downey (Victoria University of Wellington, New Zealand)

Jörg Flum (Albert-Ludwigs Universität Freiburg, Germany)


Isolde Adler (University of Leeds, UK)

Mikołaj Bojańczyk (University of Warsaw, Poland)

Benjamin Burton (The University of Queensland, Australia)

Samuel Buss (UC San Diego, USA)

Hubie Chen (Univ. Pais Vasco and Ikerbasque, Spain)

Yijia Chen (Fudan University, China)

Bruno Courcelle (LaBRI/ Bordeaux University, France)

Radu Curticapean (Hungarian Academy of Sciences, Hungary)

Anuj Dawar (University of Cambridge, UK)

Holger Dell (Saarland University, Germany)

Rodney Downey (Victoria University of Wellington, New Zealand)

Kord Eickmeyer (Technische Universität Darmstadt, Germany)

Jörg Flum (Albert-Ludwigs Universität Freiburg, Germany)

Jiawei Gao (UC San Diego, USA)

Serge Gaspers (The University of New South Wales, Australia)

Petr Hliněný (Masaryk University, Czech Republic)

Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands)

Valentine Kabanets (Simon Fraser University, Canada)

Antonina Kolokolova (Memorial University of Newfoundland, Canada)

Janos Makowsky (Technion – Israel Institute of Technology, Israel)

Catherine McCartin (Massey University, New Zealand)

Michał Pilipczuk (University of Warsaw, Poland)

Frank Stephan (National University of Singapore, Singapore)

Osamu Watanabe (Tokyo Institute of Technology, Japan)

Keita Yokoyama (Japan Advanced Institute of Science and Technology, Japan)


Sunday, September 17

15:00 Check-in

19:00 Welcome Banquet

Monday, September 18

9:00-10:00 Introduction

10:00-11:00 Bruno Courcelle: Tree-width, clique-width and fly-automata (slides)

11:00-12:00 Mikołaj Bojańczyk: A proof of Courcelle’s conjecture on recognisable graph classes

12:00 Lunch

13:30 Group Photo

14:00-15:00 Michał Pilipczuk: Definability and recognizability for graphs of bounded linear cliquewidth (slides)

15:00-15:30 Coffee Break

15:30-16:30 Petr Hliněný: Definability of path- and branch decompositions: another view

18:00 Dinner

Tuesday, September 19

9:00-10:00 Hubie Chen: One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries

10:00-10:30 Coffee Break

10:30-11:30 Isolde Adler: Testing logically defined properties on structures of bounded degree

12:00 Lunch

14:00-15:00 Kord Eickmeyer: Logics with invariantly used relations (slides)

15:00-15:30 Coffee Break

15:30-16:30 Yijia Chen: Parameterized AC– some upper and lower bounds (slides)

18:00 Dinner

Wednesday, September 20

9:00-10:00 Samuel Buss: Some NP functions and their proof complexity and completeness (slides)

10:00-10:30 Coffee Break

10:30-11:30 Valentine Kabanets: The uncanny usefulness of constructive proofs of pseudorandomness (slides)

12:00 Lunch

14:00 Excursion: Engaku and Kencho Temple

18:00 Main Banquet

Thursday, September 21

9:00-10:00 Johann Makowsky: The distinctive power and complexity of counting generalized colorings: new results and challenges (slides)

10:00-10:30 Coffee Break

10:30-11:30 Anuj Dawar: the symmetry barrier in combinatorial optimization (slides)

12:00 Lunch

14:00-15:00 Antonina Kolokolova: Proof complexity of SMT (slides)

15:00-15:30 Coffee Break

15:30-16:30 Jiawei Gao: Completeness and improved algorithms for first-order properties on sparse structures

18:00 Dinner

Friday, September 22

9:00-10:00 Frank Stephan: Deciding parity games in quasipolynomial time (slides)

10:00-10:30 Coffee Break

10:30-11:30 Benjamin Burton: TBA

12:00 Lunch

14:00 – 18:00 Free Discussion and Departure


The discipline of theoretical computer science has its early roots in the pioneering work of Church, Turing, and Gödel. Two important branches of theoretical computer science were already visible right from the beginning: One oriented to computational complexity and algorithms, the other to logic, semantics, and formal methods. The two branches have quite different goals and problems, each developed methods of its own, and they partly use different mathematical tools. Even though their division has been growing steadily during the last 30 years, the two branches come together from time to time as witnessed by the work in areas as descriptive theory, proof complexity, and more recently, parameterized complexity. The main focus of the planned meeting are those areas.

In this Shonan meeting, we aim to bring together researchers from both communities, complexity and logic, working in the areas mentioned above. So they can share their recent work and discuss research problems. The meeting will consist a number of tutorials, survey talks, and research talks.