Thu, 25 Nov 2021
11:30
C3

Relating Structure to Power

Samson Abramsky
(University College London)
Further Information

This is an in-person seminar.

Abstract

In this talk, we describe some recent work on applying tools from category theory in finite model theory, descriptive complexity, constraint satisfaction, and combinatorics.

The motivations for this work come from Computer Science, but there may be something of interest for model theorists and other logicians.

The basic setting involves studying the category of relational structures via a resource-indexed family of adjunctions with some process category - which unfolds relational structures into treelike forms, allowing natural resource parameters to be assigned to these unfoldings.

One basic instance of this scheme allows us to recover, in a purely structural, syntax-free way:

- the Ehrenfeucht-Fraisse game

- the quantifier rank fragments of first-order logic

- the equivalences on structures induced by (i) the quantifier rank fragments, (ii) the restriction to the existential-positive part, and (iii) the extension with counting quantifiers

- the combinatorial parameter of tree-depth (Nesetril and Ossona de Mendez).

Another instance recovers the k-pebble game, the finite-variable fragments, the corresponding equivalences, and the combinatorial parameter of treewidth.

Other instances cover modal, guarded and hybrid fragments, generalized quantifiers, and a wide range of combinatorial parameters.

This whole scheme has been axiomatized in a very general setting, of arboreal categories and arboreal covers.

Beyond this basic level, a landscape is beginning to emerge, in which structural features of the resource categories, adjunctions and comonads are reflected in degrees of logical and computational tractability of the corresponding languages.

Examples include semantic characterisation and preservation theorems, Lovasz-type results on  isomorphisms, and classification of constraint satisfaction problems.

Indirect search for dark matter in the Galactic Centre with IceCube
Iovine, N Journal of Instrumentation volume 16 issue 9 c09009 (01 Sep 2021)
Mon, 22 Nov 2021

16:00 - 17:00
L6

A Smörgåsbord of Number Theory (pre-PhDs Encouraged!)

George Robinson, Nadav Gropper, Michael Curran, Ofir Gorodetsky
Abstract

The speakers will be giving short presentations introducing topics in algebraic number theory, arithmetic topology, random matrix theory, and analytic number theory.

Undergrads and Master's students are encouraged to come and sample a taste of research in these areas.

 

Ancient solutions in Lagrangian mean curvature flow
Lambert, B Lotay, J Schulze, F ANNALI DELLA SCUOLA NORMALE SUPERIORE DI PISA-CLASSE DI SCIENZE volume 22 issue 3 1169-1205 (01 Jan 2021)
Spinors, twistors and classical geometry
Hitchin, N Symmetry, Integrability and Geometry: Methods and Applications volume 17 (10 Oct 2021)
Analytic Hochschild-Kostant-Rosenberg Theorem
Kelly, J Kremnizer, K Mukherjee, D (05 Nov 2021)
Conformal Maps and Geometry Beliaev, D (26 Dec 2019)
Markov chain approximations to stochastic differential equations by recombination on lattice trees
Cosentino, F Oberhauser, H Abate, A (05 Nov 2021)
Proper scoring rules, gradients, divergences, and entropies for paths and time series
Bonnier, P Oberhauser, H (11 Nov 2021)
Subscribe to