Autumn Semester HS2026

Unless stated otherwise, all talks will take place in room ExWi 228 of the Exakte Wissenschaft Building (ExWi) at the University of Bern.

Schedule

Abstracts

A well-studied phenomenon in network theory since the 1970s are optimal schedules to distribute information by one-to-one communication between nodes that are connected in the network. One can take these communicative actions to be telephone calls, and protocols to spread information this way are known as gossip protocols or epidemic protocols. A common abstraction is to call the information of each agent its secret, and that the goal of information dissemination is that all agents know all secrets: that is the termination condition of gossip protocols. Following investigations assuming a global scheduler, it is now typically assumed that gossip protocols are distributed in some way, where the only role of the environment is to ensure randomization. Statistical approaches to gossip have taken a large flight since then, wherein network topology is an important parameter.
In epistemic gossip protocols, an agent (node) will call another agent not because it is so instructed by a scheduler, or at random, but based on its knowledge or ignorance of the distribution of secrets over the network and of other agents’ knowledge or ignorance of that. One such protocol requires that an agent may only call another agent if it does not know the other agent’s secret. Epistemic features of gossip protocols may affect their termination, the (order of complexity) expectation of termination, their reachability (what distributions of secrets may occur before all agents know all secrets), and so on. Variations involve agents exchanging telephone numbers in addition to agents exchanging secrets (which results in network expansion), agents exchanging knowledge about secrets, common knowledge of the protocol, agents communicating by full information protocols, and gossip protocols with errors and error correction. We present a survey of distributed epistemic gossip protocols.
'Reasoning about Gossip' is also the title of a textbook that will appear January 2027 as volume 64 of Cambridge Tracts in Theoretical Computer Science published by Cambridge University Press. A website for the book is reasoningaboutgossip.eu.

BIO
Hans van Ditmarsch is emeritus senior researcher (directeur de recherche) at CNRS in France, and visiting professor at IIT (Indian Institute for Technology) Kanpur in India. He lives in the Netherlands. He is visiting Thomas Studer's group at University Bern in the months of September and October 2026.

Associated with any variety 𝑉 is a family of equational consequence relations that can be described in terms of congruences of 𝑉-free algebras, providing a bridge between algebraic and logical properties. Many logics admit algebraic semantics in terms of such equational consequence relations, where the underlying varieties are varieties of residuated lattices. In this setting, the consequence relations can be described via normal multiplicative filters of 𝑉-free algebras rather than congruences.

When 𝑉 is a variety of commutative residuated lattices, the associated family of consequence relations satisfies several desirable interpolation properties. In the non-commutative setting, however, these properties may fail. Motivated by this discrepancy, a consequence relation was introduced in which consequence is described via multiplicative filters, rather than normal multiplicative filters, of 𝑉-free algebras. The guiding objective was to retain a close connection with the standard equational consequence relation while recovering interpolation properties that are lost in the non-commutative setting.

In this talk, I will present the elementary properties of this consequence relation. In particular, I will discuss when it satisfies an important local deduction property and present a weak form of amalgamation satisfied by a variety whenever the associated consequence relation satisfies the Robinson property.

In this talk, I will discuss the finite model property (FMP) for superintuitionistic and modal logics. I will begin with some simple examples of logics without the FMP. I will then introduce the notion of the degree of FMP, analogous to the degree of (Kripke) incompleteness for modal logics introduced by Fine (1974). Two logics are regarded as equivalent if their classes of finite frames coincide; the degree of FMP of a logic is the cardinality of its equivalence class.
I will show that, in contrast to Blok’s Dichotomy Theorem (1978), every nonzero countable cardinal, as well as the continuum, can be realized as the degree of FMP of some superintuitionistic or transitive modal logic. This resolves a variant of an open problem in which the degree of incompleteness is replaced by the degree of FMP. This part of the talk is based on joint work with Guram Bezhanishvili and Tommaso Moraschini.
In the final part of the talk, I will show that, without assuming the Continuum Hypothesis, the degree of FMP of every superintuitionistic or modal logic is either countable or equal to the continuum. The proof uses well-known results from descriptive set theory. This part is based on joint work with Juan Aguilera and Tenyo Takahashi.

Agents A,B,C draw, respectively, 3,3,1 cards from a stack of seven known cards 0,...,6. Can A and B communicate their hand of cards to each other by public communications without C getting to know a single card? Such cards cryptography originated in analyses of bidding in bridge (1980s, Peter Winkler). This particular problem featured in the Moscow Mathematics Olympiad in 2000. I came to know about it in 2001: certain incorrect answers given by Moscow participants could be explained by an analysis in dynamic epistemic logic. It thus became known as the Russian Cards Problem. The Moscow jury's intended, correct, five triple solution is not a design and involves number theory. I found out later, after misnaming the problem, that a seven triple solution of this problem is a design and known as Kirkman's School Girl Problem (1846), laying the foundation for combinatorics. (I also found out more than 20 years later that Roman Kuznets was one of the graduate students assessing the Olympiad's answers.) A fair number purely combinatorial (non-logical) works have since seen the light, on the more general problem that three players A,B,C draw resp. i,j,k cards from a stack of i+j+k cards, where two among them wish to openly communicate their hands without the third learning a single card - despite many general cases, the full characterization of this problem is still unknown; and on the even more general problem involving n players. Further variations involve learning some but not all cards, (mere) secret bit exchange, and ordered sets of cards and protocols to learn the most valuable card. Some works that will be presented are listed below.

References:
Hans van Ditmarsch: The Russian Cards Problem. Stud Logica 75(1): 31-62 (2003)
Michael Albert, Robert Aldred, Mike Atkinson, Hans van Ditmarsch, Chris Handley: Safe communication for card players by combinatorial designs for two-step protocols. Australas. J Comb. 33: 33-46 (2005)
Andrés Cordón-Franco, Hans van Ditmarsch, David Fernández-Duque, Fernando Soler-Toscano: A colouring protocol for the generalized Russian cards problem. Theor. Comput. Sci. 495: 81-95 (2013)
Colleen Swanson, Douglas Stinson: Combinatorial solutions providing improved security for the generalized Russian cards problem. Des. Codes Cryptogr. 72(2): 345-367 (2014)
David Fernández-Duque, Valentin Goranko: Secure aggregation of distributed information: How a team of agents can safely share secrets in front of a spy. Discret. Appl. Math. 198: 118-135 (2016)
Hans van Ditmarsch, David Fernández-Duque, Vaishnavi Sundararajan, S.P. Suresh: Who holds the best card? Secure communication of optimal secret bits. Australas. J Comb. 80: 1-29 (2021)
Sergio Rajsbaum: A distributed computing perspective of unconditionally secure information transmission in Russian cards problems. Theor. Comput. Sci. 952: 113761 (2023)

Dynamic Epistemic Logic (DEL) is a family of logics that extend modal logic to model both knowledge and its change through communication. From a semantic perspective, a knowledge state is modeled by an epistemic model composed of possible worlds, and communication events update such a state by modifying the structure of the model. A central example is Public Announcement Logic (PAL) where so-called public announcements update the model by eliminating worlds. This makes PAL's semantics inherently dynamic.
In this talk, I will present a method to proof-theoretically represent the dynamic character of public announcements in a fully natural way and with only syntactical means. I will first introduce so-called indexed dynamic hypersequents that serve as a syntactic counterpart to epistemic models and their updates. I will introduce them step by step, starting from standard sequents, and highlight the underlying semantic intuitions. Within this framework, I construct a dynamic proof calculus for PAL which rules are fully natural when compared to the semantics of PAL, and reflect the structural properties of updates through public announcements, in particular how updated models are constructed and how worlds are related across such models. The calculus enjoys strong structural properties such as admissibility of all its structural rules and syntactic cut-elimination. This makes the calculus suitable for proving important meta-properties and for extension to other dynamic epistemic logics. In particular, I will show how to enrich indexed dynamic hypersequents so as to provide a calculus for the richer Logic of Epistemic Actions, where communication is not limited to public announcements.
The talk is based on a joint work with Francesca Poggiolesi.