We are happy to announce that BCTCS is coming back to Swansea next year. More details to follow.

# Author Archives: OP

# Our PhD students to present at BCTCS2021

Arved will give a talk on Propagator Networks for Unification and Proof Search on Monday (29.03) and Jay will present his research on Trustable Machine Learning Systems on Tuesday (30.03).

# Talk by Adam Ó Conghaile

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 [1], 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. [2]

[1] – S. Abramsky, A. Dawar, P. Wang *The pebbling comonad in finite model theory*, LiCS 2017

[2] – A. Ó Conghaile, A. Dawar *Game comonads & generalised quantifiers*, CSL 2021

# Celebrating World Logic Day at Swansea

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.

# Tonicha is speaking at UW-Madison logic seminar

Our PhD student, Tonicha Crook, is giving a talk at UW-Madison logic seminar today at 3pm.

__Title:__

The Weihrauch Degree of Finding Nash Equilibria in Multiplayer Games

__Abstract:__

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.

# Join The Russell Club

We are glad to announce that * The Russell Club*, a new fortnightly workshop series organized by Faron Moller, Markus Roggenbach and John Tucker, are starting next Monday (6pm-7pm).

The Russell Club is an informal Workshop Series where gems from the Foundations of Computer Science are explored. It is open and accessible to all students, be they first-years or postgraduate, from any discipline. All that is required is an inquisitive mind.

# Seventeenth International Conference on Computability and Complexity in Analysis

This week (9.09-11.09) the Seventeenth International Conference on Computability and Complexity in Analysis (CCA) is taking place virtually via Microsoft Teams (originally planned for Bologna, Italy).

Arno Pauly is among the invited speakers. He will give a talk on Weinrauch complexity this Friday.

# CCC 2020

A number of Swansea theory group members are attending the CCC 2020 (Continuity, Computability, Constructivity – From Logic to Algorithms) conference, taking place from 31 August to 4 September via Zoom. Their work will be presented in the following talks:

- Ulrich Berger, Andrew Lawrence and Monika Seisenberger
*Towards the extraction of clause learning* - Tonicha Crook and Arno Pauly
*Finding Roots of Polynomials* - Arno Pauly
*On the non-existence of some universal spaces*

CCC conference series are linked to the CID project that Swansea University actively participates in the recent years. This year the conference features talks by a number of invited speakers:

- Holger Boche (Munich)
- Elvira Mayordomo (Zaragoza)
- Eike Neumann (Oxford)
- Hideki Tsuiki (Kyoto)

# Working remotely but staying together

# Tonicha at CiE

Our PhD student Tonicha Crook attended her first CIE conference and gave an interesting talk on *The Weihrauch degree of finding Nash Equilibria in multiplayer games.*

First CiE conference this year was great and full of interesting talks! Happy to have been part of the informal presentations. Hopefully next year I can meet everyone in person @AssociationCiE @AimlaCcommunity pic.twitter.com/CboAATtgYh

— Tonicha Crook (@TonichaCrook) July 2, 2020