Difference between revisions of "Public:Seminar"

m
m (→‎Upcoming)
 
(89 intermediate revisions by 2 users not shown)
Line 2: Line 2:
=== Upcoming ===
=== Upcoming ===


(If you have any suggestions for talks, get in touch!)
⚫
* 31 March 2022: '''Dan Marsden''' will talk about multimorphisms

* 7 April 2022: '''Luca Reggio''' will talk about preservation theorems
* soon Adam Bartoš will talk about a categorical Fraisse theory
⚫
* 14 April 2022: we will have a general discussion regarding the future of the project
* Amir Tabatabai
* Benedikt Pago -- speaking about his recent [https://arxiv.org/abs/2308.05693 homomorphism indistinguishability] result
* in December, Luca will give a talk
* after Christmas, Dan will give a talk

And at some point later on

* Amin Karamlou could talk about quantum model comparison games or string diagrams for distributive laws
* Nicolas Wu will speak about co-effects
* Dan will talk about bialgebraic semantics
* Dan will give a tutorial on Street's formal monad theory
* Tomas will talk about locality or PCSP
<!--
and possibly also:

* Tomas will talk about Adjunctions and a comonad in the Wonderland of (P)CSPs
* Tomas will spark a discussion about the implicative fragment and tgds

Would be nice to have

Adam Bartos - categorical Fraisse theory

Chris Heunen or Carmen tell us about localisable monads? https://homepages.inf.ed.ac.uk/cheunen/publications/2021/localisable/localisable.pdf or https://arxiv.org/abs/2108.01756

Bartosz Jan Bednarczyk

Marcelo Fiore's work on generalised equational theories and connections with monads

Andy Pitts?

Martin Otto
Albert Atserias

-->


=== Previous ===
=== Previous ===

==== 2023 ====
* 14 June 2023: '''[https://arkor.co/ Nathanael Arkor]''' talked about the theory of relative (co)monads <!-- abstract: Relative (co)monads were introduced by Altenkirch, Chapman and Uustalu [1], generalising the notion
of (co)monad to the setting in which the underlying functor is not required to be an endofunctor. In
the past decade, relative (co)monads have received much attention, particularly in applications to
computer science, and their usefulness as a tool for the working category theorist is becoming
increasingly clear. In this talk, I will give an overview of my ongoing work with Dylan McDermott,
in which we have been developing a general theory of relative (co)monads [2, 3]. My intention is to
provide a toolkit of useful results for dealing with relative (co)monads. If time permits, I will
explain how the general theory of the talk may be applied to give an elegant treatment of
monad–theory correspondences [4].

Some basic familiarity with category theory will be assumed.

[1] Monads need not be endofunctors (https://arxiv.org/abs/1412.7148)
[2] The formal theory of relative monads (https://arxiv.org/abs/2302.14014)
[3] Relative monadicity (https://arxiv.org/abs/2305.10405)
[4] Monadic and Higher-Order Structure (https://doi.org/10.17863/CAM.86347) --> '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/2/25/2023-06-14_-_Nathanael_Arkor_-_The_theory_of_relative_%28co%29monads.pdf (slides)]'''
* 26 April 2023: '''Tim Seppelt''' talked about Homomorphism Indistinguishability for Comonadists <!-- abstract: Lovász (1967) showed that two graphs $G$ and $H$ are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph $F$, the number of homomorphisms from $F$ to $G$ is equal to the number of homomorphisms from $F$ to $H$. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth, and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems.

This talk's starting point will be an overview of how (bi)labelled graphs, homomorphism tensors, and linear-algebraic techniques can be used to build matrix equations for homomorphism indistinguishability (ICALP 2022, SODA 2023). Motivated by the plenitude of equivalence on graphs which can be characterised as homomorphism indistinguishability relations, we will then touch upon steps towards a theory of homomorphism indistinguishability including Roberson's conjecture and correspondences between syntax and semantics.

Many notions used in recent work to deepen the understanding of homomorphism indistinguishability have an interpretation in terms of game comonads and related objects. This talk covers some of these connections.--> '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/custom/2023-04-26_-_Tim_Seppelt_-_Homomorphism_Indistinguishability_for_Comonadists.pdf (slides)]'''
* 15 March 2023: '''[https://bmbumpus.com Benjamin Bumpus]''' talked about Chopping things up to decide stuff fast '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/custom/2023-03-15_-_Benjamin_M_Bumpus_-_Choping_stuff_up_to_decide_things_fast.pdf (slides)]'''.
* 22 Feb 2023: '''[https://fredrikdahlqvist.wordpress.com/ Fredrik Dahlqvist]''' will talk about "How to write a coequation" '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/d/da/2023-02-22_-_Fredrik_Dahlqvist_-_How_to_write_a_coequation_%28slides%29.pdf (slides)]'''
* 1 Feb 2023: '''[https://www8.cs.fau.de/people/chase-ford/ Chase Ford]''' will talk about Graded Monads and Behavioural Equivalence Games [https://arxiv.org/abs/2203.15467 arXiv:2203.15467] '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/1/1c/2023-02-01_-_Chase_Ford_-_Graded_Monads_and_Behavioural_Equivalence_Games_%28slides%29.pdf (slides)]'''

==== 2022 ====

* 16 November 2022: '''Tarmo Uustalu''' talked about Additive cellular automata graded-monadically '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/2/27/2022-11-16_-_Tarmo_Uustalu_-_Additive_cellular_automata_graded-monadically_%28slides%29.pdf (slides)]'''
* 12 October 2022: '''Bartek Klin''' talked about [https://arxiv.org/abs/1907.09634 Codensity Games for Bisimilarity]
* 5 October 2022: '''Tomas''' talked about adding an open problem of Mai Gehrke and other questions concerning adding a layer of quantifiers comonadically
* 21-23 September 2022: A [[Project meetings#21-23_September_2022|kick-off meeting]] of the Resources in Computation project
* 14 September 2022: '''Amin Karamlou''' talked about degrading the quantum monad and monad-comonad distributive laws. <!-- abstract: In the first part of the talk I will survey work on how one can “degrade” graded monads to obtain related normal monads. We will then use these techniques to obtain a degraded variant of the quantum monad of Abramsky et al. We then show that many well-known comonads do not distribute over this degraded variant of the quantum monad.

In the second part of the talk we consider mixed distributive laws of the form MW \rightarrow WMMW→WM for monads MM and comonads WW. We prove that such distributive laws exist for a large class of probability monads and container comonads. This result is in sharp contrast to our no-go theorems for comonad-monad distributive laws which I presented in an earlier seminar talk. -->
* 4 July 2022: [https://www.cst.cam.ac.uk/conference/structure-meets-power-2022 Structure Meets Power 2022 workshop]
* 29 June 2022: '''[https://agoy.fr/ Alexandre Goy]''' talked about Weakening distributive laws using string diagrams <!-- abstract: Monads are usually composed using distributive laws. If a no-go theorem forbids such a law to exist, there may still be ways to get something looking like a composite monad. This is the purpose of weak distributive laws. In this talk, I will introduce different weakenings of distributive laws and show how string diagrams can help reason about them, using the example of iterated weak distributive laws. -->
* 22 June 2022: '''Nihil Shah''' spoke about Linear modal comonad and arboreal categories (joint with Samson and Yoàv) '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/2/27/2022-06-22-Shah_-_Linear_modal_comonad_and_linear_arboreal_%28slides%29.pdf (slides)]''' <!-- abstract: A key part of the categorical semantics provided by Spoiler-Duplicator game comonads utilizes the arboreal category structure, axiomatized by Abramsky and Reggio, of their category of coalgebras. Arboreal categories admit a categorical notion of bisimulation. In this talk, I will discuss ongoing work on a notion of linear arboreal category. This notion generalizes the connection between the pebble-relation comonad and the pebbling comonad. As another simpler example, we develop a notion of linear modal comonad which captures trace inclusion, trace equivalence, and another weaker behavioral equivalence. -->
* 15 June 2022: '''Amin Karamlou''' will talk about No-Go Theorems For Mixed Distributive Laws: Containers over Non-determinism <!-- abstract: Monads and comonads are important constructions of category theory which find widespread application in computer science and other related disciplines. Distributive laws allow these constructions
to interact compositionally. Such laws are not guaranteed to exist, and even when they do, finding them can be a difficult and time consuming task.

Inspired by recent results which establish conditions under which no distributive laws can exist between pairs of monads, we present a family of no-go theorems for the existence of mixed distributive laws between a comonad and a monad. -->
* 8 June 2022: '''Samson Abramsky''' gave a talk titled "From Kochen-Specker to Feder-Vardi" (Joint work with Adam Ó Conghaile and Anuj Dawar), had a large overlap with [https://arxiv.org/abs/2206.12156 arXiv:2206.12156]
* 1 June 2022: '''Achim Blumensath''' gave a tutorial on the composition method
* 25 May 2022: [https://elenadilavore.github.io/ Elena di Lavore] will talk about Monoidal Width '''[https://kam.mff.cuni.cz/~jaklt/comonadwiki/images/custom/2022-05-25-Di_Lavore_-_Monoidal_Width.pdf (slides)]''' <!-- Abstract: We introduce monoidal width as a measure of the difficulty of decomposing morphisms in monoidal categories. By instantiating monoidal width and two variations a suitable category of cospans of graphs, we capture existing notions, namely branch width, tree width and path width. By changing the category of graphs, we are also able to capture rank width. Through these and other examples, we propose that monoidal width: (i) is a promising concept that, while capturing known measures, can similarly be instantiated in other settings, avoiding the need for ad-hoc domain-specific definitions and (ii) comes with a general, formal algebraic notion of decomposition using the language of monoidal categories. -->
* 11 May 2022: '''Rafal Stefanski''' talked about single-use Automata for Infinite Alphabets <!-- Abstract: Register automata (as defined by Kaminski & Frances) are a well-established model for recognizing languages over infinite alphabets. They define a class of languages which shares many desirable properties of regular languages, but their definition is not as stable as the one of finite automata – for example, all the following variants of register automata define pairwise nonequivalent classes of languages: deterministic one-way, deterministic two-way, nondeterministic one-way, and nondeterministic two-way. In this talk, I am going to introduce the single-use restriction for register automata which states that every read access to a register should have the side effect of destroying that register’s content. I am going to argue that the single-use version of register automata defines a robust class of languages. In particular, with the single-use restriction in place, one-way and two-way deterministic register automata recognize the same class of languages. The talk is based on a joint research with Mikołaj Bojańczyk and Nathan Lhote. -->
⚫
* 4 May 2022: we had a general discussion regarding the future of the project, led by '''Tomas Jakl'''
⚫
* 27 April 2022: '''Dan Marsden''' talked about bimorphisms and FVM theorems
* 20 April 2022: '''Luca Reggio''' talked about arboreal categories and homomorphism preservation theorems '''[[:File:2022-04-20 - Luca Reggio - Arboreal categories and homomorphism preservation theorems.pdf|(slides)]]'''
* 13 April 2022: '''Tomas Jakl''' led a discussion on comonadic tools in [https://arxiv.org/abs/2004.14789 Twin-Width I]
* 15-16 March 2022: [[Project meetings|Project Meeting]]

==== 2021 ====


* 9 December 2021: '''Tomas Jakl''' talked about A game comonads' perspective on Courcelle and Feferman-Vaught-Mostowski theorems, '''[[:File:2021-12-09 - A game comonads perspective on Courcelle and Feferman-Vaught-Mostowski theorems (Tomas).pdf|(slides)]]'''
* 9 December 2021: '''Tomas Jakl''' talked about A game comonads' perspective on Courcelle and Feferman-Vaught-Mostowski theorems, '''[[:File:2021-12-09 - A game comonads perspective on Courcelle and Feferman-Vaught-Mostowski theorems (Tomas).pdf|(slides)]]'''
Line 13: Line 101:
* 21 October 2021: '''Luca Reggio''' talked about Polyadic sets and homomorphism counting
* 21 October 2021: '''Luca Reggio''' talked about Polyadic sets and homomorphism counting
* 21 October 2021: '''Samson Abramsky''' talked about Cohomology for Everyone
* 21 October 2021: '''Samson Abramsky''' talked about Cohomology for Everyone
* 16-17 September 2021: [[Project meetings|Project Meeting]]
* 27-28 June 2021: [https://www.cst.cam.ac.uk/conference/structure-meets-power-2021 Structure meets Power Workshop]
* 22 April 2021: '''Tomas Jakl''' talked about [[Discrete density comonads]] (and combinatorial properties), '''[[:File:2021-04-22 - Discrete density comonads (Tomas).pdf|(slides)]]'''
* 22 April 2021: '''Tomas Jakl''' talked about [[Discrete density comonads]] (and combinatorial properties), '''[[:File:2021-04-22 - Discrete density comonads (Tomas).pdf|(slides)]]'''
* 25 March 2021: '''Luca Reggio''' continued with an Introduction to Arboreal Categories (part II)
* 25 March 2021: '''Luca Reggio''' continued with an Introduction to Arboreal Categories (part II)
Line 18: Line 108:
* 11 March 2021: '''Nihil Shah''' talked about Metrics on the homomorphism order
* 11 March 2021: '''Nihil Shah''' talked about Metrics on the homomorphism order
* 4 March 2021: '''Anuj Dawar''' talked about Invertible Map Games and Linear Algebraic Quantifiers, '''[[:File:2021-03-21 - Invertible Map Games and Linear Algebraic Quantifiers (Anuj).pdf|(slides)]]'''
* 4 March 2021: '''Anuj Dawar''' talked about Invertible Map Games and Linear Algebraic Quantifiers, '''[[:File:2021-03-21 - Invertible Map Games and Linear Algebraic Quantifiers (Anuj).pdf|(slides)]]'''

==== 2020 ====

* 3 December 2020: '''Nihil Shah''' talked about progress on pebble-relation comonad
* 3 December 2020: '''Nihil Shah''' talked about progress on pebble-relation comonad
* 12 November 2020: '''Dan Marsden''' talked about acyclicity in finite Kripke structures
* 12 November 2020: '''Dan Marsden''' talked about acyclicity in finite Kripke structures
Line 40: Line 133:
* 23 April 2020: '''Tom Paine''' talked about Interpreting comonads as adjunctions into modal logic
* 23 April 2020: '''Tom Paine''' talked about Interpreting comonads as adjunctions into modal logic
* 9 April 2020: '''Adam Ó Conghaile''' talked about Game comonads and generalised quantifiers
* 9 April 2020: '''Adam Ó Conghaile''' talked about Game comonads and generalised quantifiers
* 26 March 2020: [https://www.cst.cam.ac.uk/conference/coresources-2020/online-workshop Online Workshop on Resources and Co-Resources]

Latest revision as of 18:14, 18 November 2023

Upcoming

(If you have any suggestions for talks, get in touch!)

  • soon Adam Bartoš will talk about a categorical Fraisse theory
  • Amir Tabatabai
  • Benedikt Pago -- speaking about his recent homomorphism indistinguishability result
  • in December, Luca will give a talk
  • after Christmas, Dan will give a talk

And at some point later on

  • Amin Karamlou could talk about quantum model comparison games or string diagrams for distributive laws
  • Nicolas Wu will speak about co-effects
  • Dan will talk about bialgebraic semantics
  • Dan will give a tutorial on Street's formal monad theory
  • Tomas will talk about locality or PCSP

Previous

2023

2022

  • 16 November 2022: Tarmo Uustalu talked about Additive cellular automata graded-monadically (slides)
  • 12 October 2022: Bartek Klin talked about Codensity Games for Bisimilarity
  • 5 October 2022: Tomas talked about adding an open problem of Mai Gehrke and other questions concerning adding a layer of quantifiers comonadically
  • 21-23 September 2022: A kick-off meeting of the Resources in Computation project
  • 14 September 2022: Amin Karamlou talked about degrading the quantum monad and monad-comonad distributive laws.
  • 4 July 2022: Structure Meets Power 2022 workshop
  • 29 June 2022: Alexandre Goy talked about Weakening distributive laws using string diagrams
  • 22 June 2022: Nihil Shah spoke about Linear modal comonad and arboreal categories (joint with Samson and Yoàv) (slides)
  • 15 June 2022: Amin Karamlou will talk about No-Go Theorems For Mixed Distributive Laws: Containers over Non-determinism
  • 8 June 2022: Samson Abramsky gave a talk titled "From Kochen-Specker to Feder-Vardi" (Joint work with Adam Ó Conghaile and Anuj Dawar), had a large overlap with arXiv:2206.12156
  • 1 June 2022: Achim Blumensath gave a tutorial on the composition method
  • 25 May 2022: Elena di Lavore will talk about Monoidal Width (slides)
  • 11 May 2022: Rafal Stefanski talked about single-use Automata for Infinite Alphabets
  • 4 May 2022: we had a general discussion regarding the future of the project, led by Tomas Jakl
  • 27 April 2022: Dan Marsden talked about bimorphisms and FVM theorems
  • 20 April 2022: Luca Reggio talked about arboreal categories and homomorphism preservation theorems (slides)
  • 13 April 2022: Tomas Jakl led a discussion on comonadic tools in Twin-Width I
  • 15-16 March 2022: Project Meeting

2021

  • 9 December 2021: Tomas Jakl talked about A game comonads' perspective on Courcelle and Feferman-Vaught-Mostowski theorems, (slides)
  • 25 November 2021: Algorithms Discussion II
  • 11 November 2021: Algorithms Discussion
  • 21 October 2021: Luca Reggio talked about Polyadic sets and homomorphism counting
  • 21 October 2021: Samson Abramsky talked about Cohomology for Everyone
  • 16-17 September 2021: Project Meeting
  • 27-28 June 2021: Structure meets Power Workshop
  • 22 April 2021: Tomas Jakl talked about Discrete density comonads (and combinatorial properties), (slides)
  • 25 March 2021: Luca Reggio continued with an Introduction to Arboreal Categories (part II)
  • 18 March 2021: Samson Abramsky gave an Introduction to Arboreal Categories (part I)
  • 11 March 2021: Nihil Shah talked about Metrics on the homomorphism order
  • 4 March 2021: Anuj Dawar talked about Invertible Map Games and Linear Algebraic Quantifiers, (slides)

2020

  • 3 December 2020: Nihil Shah talked about progress on pebble-relation comonad
  • 12 November 2020: Dan Marsden talked about acyclicity in finite Kripke structures
  • 22 October 2020: Samson Abramsky talked about his recent work on open span bisimulation
  • 15 October 2020: Luca Reggio talked about (locally) finitely presentable categories
  • 8 October 2020: Tom Paine talked about Courcelle’s theorem, covering the regular approach, a game theoretic approach, and how it's related to Comonads
  • 24 September 2020: Adam Ó Conghaile talked about Brambles, havens, shelters, and other obstructions to nice decompositions: where do they fit in the world of game comonads?
  • 17 September 2020: Tomas Jakl talked about 3 new Lovasz-type results
  • 3 September 2020: Louis Parlant from the UCL talked about his recent PhD work on general methods for composing monads via distributive laws
  • 13 August 2020: Dan Marsden talked about some simple observations relating to modal logics and model constructions within our setting (early work in progress)
  • 30 July 2020: Nihil Shah talked about the loosely guarded fragment and hypertree width, (notes)
  • 23 July 2020: Samson Abramsky talked about comonadic semantics for guarded fragments
  • 16 July 2020: Rui Soares Barbosa talked about the Quantum monad
  • 2 July 2020: Tom Paine talked about game comonads and locality
  • 25 June 2020: Luca Reggio talked about some of his recent work on results à la Lovász
  • 18 June 2020: Alexis Toumi, a DPhil in Oxford, gave a speculative talk about applications of game comonads for work in linguistics and cognition being conducted in our group
  • 11 June 2020: Tomas Jakl talked about "retractions" of comonads
  • 28 May 2020: Samson Abramsky talked about some of the new material in the extended journal version of his CSL paper with Nihil, (slides)
  • 14 May 2020: Luca Reggio talked about the Rossman homomorphism theorem
  • 7 May 2020: Dan Marsden talked about string diagrams
  • 30 April 2020: Nihil Shah talked about CSP
  • 23 April 2020: Tom Paine talked about Interpreting comonads as adjunctions into modal logic
  • 9 April 2020: Adam Ó Conghaile talked about Game comonads and generalised quantifiers
  • 26 March 2020: Online Workshop on Resources and Co-Resources
Retrieved from "https://kam.mff.cuni.cz/~jaklt/comonadwiki/index.php?title=Public:Seminar&oldid=3295"