Supervisor. Sam van Gool
Schedule. Tuesdays, 14:00-16:00, from September 15, 2026 until October 20, 2026, room 1X59 (except 1Z56 on 29 Sep).
Participants. TBD.
Keywords. Automata, modal logic, first- and second-order logic, graphs, theory of computation.
Skills to be developed. Reading current research articles, writing reviews, giving presentations, identifying research problems, giving feedback.
Description. This workshop is about recent research on the theory and applications of automata and logic in computer science. We will read five articles that appeared this summer in one of the top conferences in the field, Logic in Computer Science (LICS), on topics that fit with some of the above keywords.
The students in this workshop will read, summarize, write critical reviews, and give presentations on the articles. Ideally, these activities will lead us to identify open research problems, which may form the basis for a research internship proposal.
A main learning objective of the workshop is to learn how to read an article in limited time, and how to extract the main contributions and ideas from it, without getting blocked by details. In addition, the workshop will increase participants’ understanding of current research in the field, and of how theoretical computer science conferences work in practice.
Articles. Below is a list of suggested articles for this workshop. Participants are also welcome to suggest other articles of interest in recent conferences like LICS or similar. We will choose five of them in the first meeting.
- Bacik, Nieuwveld, Ouaknine, Vahanwala, Venkatesh, Wieser. On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic.
- Balabonski. A Machine-Independent, Log-Sensitive Space-Cost Measure for the Weak Lambda-Calculus.
- Bojańczyk, Casares, Manthe, Parys. Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches.
- Casares, Löding, Walukiewicz. Layered Automata: A Canonical Model for Automata over Infinite Words.
- ten Cate, Kuijer, Wolter. The Size of Interpolants in Modal Logics.
- Galatos, Jipsen, Knudstorp, Ramanayake. The Logic of Bunched Implications Is Undecidable.
- Mählmann, Siebertz. Existential Positive Transductions of Sparse Graphs.
- Yang, Bojańczyk, Klin. The Finite Length Property of the Rado Graph and Friends.
TO DO before the first meeting.
- Read the title and abstract of each of the above articles.
- Based on this, make your personal order of preference.
- Optional: send articles that you would like to add to the list by e-mail to the supervisor at svangool@ens-paris-saclay.fr.
Tasks. The first week will be devoted to an introductory discussion and organization of the rest of the workshop. After that, each week will focus on one article, and each student will perform a different task for the article, among the ones below:
- Write a review of an article: a document of 2-3 pages which includes a summary and a critical evaluation of the article, follow-up questions about the article’s contents, interesting open problems that arise from it.
- Prepare and give a twenty-five minute presentation of an article: in the style of a traditional conference presentation, give an overview of the article’s contents, at a level understandable for your peers.
- Prepare and give an eight minute presentation of an article: in the style of the Highlights conference, choose the most interesting result in an article and explain it at a level understandable for your peers.
- Act as audience member for a presentation: take notes and ask questions on the presentation’s content, and give feedback to the presenters.
- Contribute to workshop organization: design a schedule, create and maintain a shared communication channel, maintain a shared repository containing relevant documents, act as session chair.
The workload, in addition to the two-hour meetings, will be approximately three hours per week on average. It may vary somewhat, according to your task of the week.
Grades will reflect each student’s participation and effort in performing all of the above tasks.