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.

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)