Today Adam Ó Conghaile will give a talk on “Games & Comonads in Finite Model Theory” as a part of our Theory Seminar Series.
Abstract. Model-comparison games (such as Ehrenfeucht-Fraïssé games, pebble games and modal bisimulation) capture various approximations to isomorphism and homomorphism between structures. These approximations are important and well-studied in computer science for their connections with logic and algorithms but their descriptions are often ad hoc and unified approach to these games is lacking in classical finite model theory. Game comonads, introduced by Abramsky, Dawar & Wang , provide a categorical semantics for these games which reveals connections between these games and relates them in a surprising and elegant way to structural parameters such as treewidth.
In my talk, I will survey the landscape of model-comparison games and developments in this new comonadic perspective to them, including contributions from my recent work with Anuj Dawar on game comonads for logics with generalised quantifiers. 
 – S. Abramsky, A. Dawar, P. Wang The pebbling comonad in finite model theory, LiCS 2017
 – A. Ó Conghaile, A. Dawar Game comonads & generalised quantifiers, CSL 2021
Adam Ó Conghaile
I am a PhD student at the Computer Lab of the University of Cambridge. With my supervisor, Prof Anuj Dawar, I’m researching a compositional approach to finite model theory and descriptive complexity.
Roger Hindley will give a talk on “100 Years of Combinatory Logic” on Friday, 22 January 2021 as a part of the World Logic Day celebration here in Swansea.
Time: Jan 22, 2021 10:00 AM London
Join Zoom Meeting by following this link.
Meeting ID: 965 2656 4560 Passcode: 411495
UNESCO proclaimed World Logic Day in 2019 in association with the International Council for Philosophy and Human Sciences (CIPSH), to enhance public understanding of logic and its implications for science, technology and innovation.
A complete list of WLD 2021 events can be found at http://www.wld.cipsh.international/wld.html.
CIPSH: World Logic Day
This page lists events celebrating World Logic Day 2021.
Our PhD student, Tonicha Crook, is giving a talk at UW-Madison logic seminar today at 3pm.
The Weihrauch Degree of Finding Nash Equilibria in Multiplayer Games
Is there an algorithm that takes a game in normal form as input, and outputs a Nash equilibrium? If the payoffs are integers, the answer is yes, and a lot of work has been done in its computational complexity. If the payoffs are permitted to be real numbers, the answer is no, for continuity reasons. It is worthwhile to investigate the precise degree of non-computability (the Weihrauch degree), since knowing the degree entails what other approaches are available (eg, is there a randomized algorithm with positive success change?). The two player case has already been fully classified, but the multiplayer case remains open and is addressed here. As well as some insight into finding the roots of polynomials, which is essential in our research. An in-depth introduction to Weihrauch Reducibility will be included in the presentation, along with a small introduction to Game Theory.
In spite of the COVID-19 outbreak, we are glad to host BCTCS 2020 starting today, even if virtually. For more information on invited and contributed talks, check the official BCTCS 2020 website.
Our colleague Arno Pauly is on the Programme Committee of the Computability Theory and its Applications seminar series, which currently is taking place virtually.
The seminar now has a YouTube channel where you can find the recordings of past talks you may have missed. The information on future talks, the timings of those, and the links to the videos are all available on the webpage here:
CTA Seminar – Computability
The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia.
Today as a part of the 2nd World Logic Day our Theory group commemorated the work of Erik Palmgren (1963-2019), who sadly passed away last year.
Anton Setzer presented Erik’s most influential papers, which had a big impact on Anton’s own research.
We meet to remember the great logician Erik Palmgren who sadly passed away in November 2019 .
To honor Erik Palmgren’s work, Anton Setzer will give a talk with the title:
Palmgren’s interpretation of inductive definitions in type theory and development of higher type universes in type theory.
The meeting also marks the 2nd World Logic Day.
Venue: Theory Lab (CoFo 209)
Time: 14th of January 2020, 2-3 pm
Following the Summer School, we are really proud to host the 2nd Proof Society Workshop. The workshop was an opportunity to listen to a lot of interesting invited and contributed talks on proof theory and various areas of its application:
Adam Wyner: Computational Law – The Case of Autonomous Vehicles
Yong Cheng: Exploring the incompleteness phenomenon
Matthias Baaz: Towards a Proof Theory for Henkin Quantifiers
Sonia Marin: On cut-elimination for non-wellfounded proofs: the case of PDL
Gilles Dowek: Logical frameworks, reverse mathematics, and formal proofs translation
Benjamin Ralph: What is a combinatorial proof system?
William Stirton: Ordinal assignments correlated with notions of reduction
Oliver Kullmann: Practical proof theory: practical versions of Extended Resolution
Anton Setzer and Ulrich Berger on behalf of Ralph Matthes: Martin Hofmann’s case for non-strictly positive data types – reloaded
Laura Crosilla: Philosophy of mathematics and proof theory
Takako Nemoto: Recursion Theory in Constructive Mathematics
Arno Pauly: Combinatorial principles equivalent to weak induction
Antonina Kolokolova: The proof complexity of reasoning over richer domains
Joost Joosten: The reduction property revisited
Helmut Schwichtenberg: Computational content of proofs
Thanks to all the speaker and participants and we hope to see you all again soon.
Congratulations to Iris van der Giessen for winning the best poster competition and special thanks to Andreas Weiermann for the beautiful picture of Wales that serves as our main prize.
Big thanks to all the speakers and the participants for joining our Summer School. We hope to see you again during the future events by the Proof Society.
Iris van der Giessen – Best Poster
We were glad to welcome Takako Nemoto, who joined us on the second day of the Summer School and gave her course on Reverse Mathematics.
As a treat, the participants of the Summer School had a trip to Rhossili and enjoyed a walk along the Welsh coastal path with stunning views. Big thanks to Arved Friedemann and Melissa Antonnelli for the beautiful photos.