Invited Speakers

Laurent Bienvenu (Bordeaux)
Olivier Bournez (École Polytechnique)
Wesley Holliday (University of California, Berkeley)
Christian Ikenmeyer (Liverpool)
Philipp Lücke (Universität Bonn)
Margaret Thomas (West Lafayette)

Titles and Abstracts

Laurent Bienvenu

Title: New results on logical depth

Abstract: In algorithmic information theory, complexity is equated with randomness, therefore we find ourselves in a seemingly paradoxical situation where a higher complexity value is assigned to a random string of symbols than, say, Tolstoy’s novel War and Peace. Bennett’s notion of logical depth is an attempt to resolve this paradox. We will review this notion and discuss some of its important properties. We will also present several recent results (joint work with Chris Porter) that support the intuition that no reasonable stochastic process can be used to generate a deep object.

Olivier Bournez

Title: Characterizations of complexity and computability classes using ordinary differential equations.

Abstract: Initially motivated by understanding the computational power of various continuous-time analog models of computations, several characterizations of  complexity and computability classes have been obtained recently using ordinary differential equations. Basically, each class is characterized as the class of functions containing some basic functions, and closed by composition and various natural schemas or constructions, based on ordinary differential equations. We will provide a review of some of these recent results. We will both consider classical ordinary differential equations, and their discrete counterpart, also known as discrete ordinary differential equations, or finite differences. This will also both cover the case of classes of functions over the integers, and functions over the reals, in the framework of computable analysis.

Wesley Holliday

Title: Subsystems of classical logic and their semantics based on graphs

Abstract: The starting points of my talk are two of the most important subsystems of classical logic arising in the foundations of mathematics and foundations of physics: intuitionistic logic (Heyting 1930) and orthologic (Birkhoff and von Neumann 1936). In a Fitch-style formulation of natural deduction, intuitionistic logic and orthologic can be obtained from a more basic logic, defined using only the introduction and elimination rules for the logical connectives, by the addition of rules of Reiteration and Reductio ad Absurdum, respectively. In this talk (based on https://arxiv.org/abs/2207.06993), I will characterize this “fundamental” logic both proof-theoretically and semantically. The semantic characterization is based on representation theorems for complete lattices with additional operations (e.g., negation, implication) using directed graphs.

Christian Ikenmeyer

Title: Algebraic combinatorics in geometric complexity theory

Abstract: This talk gives an introduction to geometric complexity theory, an approach towards algebraic computational complexity lower bounds via algebraic geometry and representation theoretic multiplicities. Whether or not these multiplicities have combinatorial interpretations is a set of old open questions. We discuss approaches towards resolving these and related questions via connections to complexity theory.

Philipp Lücke

Title: Large cardinals, strong logics and reflection principles

Abstract: Various results establish strong connections between the existence of large cardinals, regularity properties of strong logics and the validity of set-theoretic reflection principles. In particular, several compactness properties of strong logics were proven to be equivalent to large cardinal axioms, and such equivalences provide strong arguments to adopt these axioms. An important example of such an equivalence is given by a theorem of Makowsky that shows that Vopenka’s Principle is equivalent to the existence of strong compactness cardinals for all abstract logics. Motivated by work of Boney, Dimopoulos, Gitman and Magidor, I recently proved an analogous combinatorial characterization of the existence of weak compactness cardinals for all abstract logics that is closely connected to the notion of subtle cardinals, introduced by Kunen and Jensen in their studies of strong diamond principles, and the concept of shrewd cardinals, defined by Rathjen in proof-theoretic work. In my talk, I want to first discuss the details of this characterization and then present a result that shows that the existence of a proper class of subtle cardinals is consistent with the axioms of ZFC if and only if the existence of weak compactness cardinals for all abstract logics does not provably imply the existence of a strongly inaccessible cardinal.

Margret Thomas

Title: Effective Pila–Wilkie bounds for Pfaffian sets

Abstract: There are by now many applications of model theory to diophantine geometry via o-minimality, arising from the celebrated counting theorem of Pila and Wilkie. This result bounds the number of rational points of bounded numerator and denominator lying on sets definable in o-minimal expansions of the real field. The proof of the Pila–Wilkie Theorem does not, however, provide an effective bound, and the pursuit of this (in instances where this question can be given meaning), motivated by the goal to improve certain diophantine applications, remains very active. I will discuss ongoing joint work (with Gal Binyamini, Gareth O. Jones and Harry Schmidt) in which we obtain effective forms of the Pila–Wilkie Theorem for sets definable in various structures described by Pfaffian functions (including an effective parameterization result for certain sets in this context), as well as a number of effective diophantine applications of these results.