LAB42 Talk | FOAM: Malvin Gattinger - The Limits to Gossip
Join us in this FOAM seminar from Malvin Gattinger from the Institute for Logic, Language and Computation.
The Limits to Gossip: Second-order Shared Knowledge of all Secrets is Unsatisfiable
It is known that without synchronization via a global clock one cannot obtain common knowledge by communication. Moreover, it is folklore that without exchanging higher-level information arbitrary higher-level shared knowledge cannot be achieved. Here we make this result precise. We use epistemic logic to formally define “everyone knows that everyone knows that everyone knows all secrets” and then prove that this statement is unsatisfiable.Joint work with Hans van Ditmarsch.
FOAM seminars
The FOAM Seminar, organised by computer scientists at the ILLC, features research on questions of a fundamental nature in computer science and AI, in research areas such as algorithms, optimisation, data management, planning, knowledge representation, and multiagent systems. Talks are intended to be broadly accessible and pitched at the level you might find at a plenary talk of a relevant conference (such as IJCAI, AAAI, KR, ICAPS, AAMAS, EC, PODS, LICS, STOC, FOCS, and SODA).
FOAM usually takes place on a Friday at 15:00. Talks are roughly 45 minutes long, followed by a brief discussion. Afterwards, you are invited to stay for a chat and a drink. Everyone is welcome to attend!