Sep 1, 2017 Comments Off on Organizers
Organizers
Yijia Chen (Fudan University, China)
Rodney Downey (Victoria University of Wellington, New Zealand)
Jörg Flum (Albert-Ludwigs Universität Freiburg, Germany)
Sep 1, 2017 Comments Off on Participants
Participants
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)
Sep 1, 2017 Comments Off on Schedule
Schedule
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 AC0 – 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
Sep 1, 2017 Comments Off on Overview
Overview
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.