Logique à Paris 2024

Talks and abstracts

Simon André:
- The first-order theory of free and hyperbolic groups
  
  Around 1945, Tarski asked whether non-abelian free groups are elementarily equivalent. This problem was solved positively two decades ago by Sela, and by Kharlampovich and Myasnikov. The geometric techniques introduced by Sela proved very powerful and were used to solve various problems about the first-order theory of free groups (homogeneity, stability, etc). Moreover, these techniques can be extended to more general classes of groups, such as Gromov hyperbolic groups. In my talks, I will present several results concerning the first-order theory of these groups.
Alexi Block Gorman:
- An introduction to some connections between model theory and automata theory.
  
  There are compelling and long-established connections between automata theory and model theory, particularly regarding expansions of Presburger arithmetic by sets whose base-$k$ representations are recognized by a finite-state automaton. We call such sets “$k$-automatic”.
  
  Büchi automata are the natural extension of finite-state automata to a model of computation that accepts infinite-length inputs. We say a subset $X$ of the reals is “$k$-regular” if there is a Büchi automaton that accepts (one of) the base-$k$ representations of every element of $X$, and rejects the base-$k$ representations of each element in its complement. These sets often exhibit fractal-like behavior–e.g., the Cantor set is $3$-regular.
  
  In this talk we will consider the expansions of Presburger arithmetic and the real additive group by $k$-automatic and $k$-regular sets respectively, and learn about what is understood (and what has been open up to now) about the geometry of their definable sets.
- Expansions of $\mathbb{R}$ and $\mathbb{N}$ by $k$-automatic sets: Choose-your-own-adventure!
  
  In this talk, we will discuss the significance of expansions of the ordered additive groups of the integers and the reals repectively by $V_{k}$ (and its reducts). In the real setting, we will discuss dividing lines in definability from the perspectives of both tame geometry and neostability. In the setting of Presburger arithmetic, we obtain a characterization of the reducts of this structure in terms of definability of the $V_k$ function and its consquences for the decidability and neostability-related properties of related structures.
Andrew Brooke-Taylor:
- Uncountable cardinals up to the continuum
  
  It is well known that the Continuum Hypothesis (CH) is independent of the ZFC set theory axioms. One stance that people may take is to assume that CH is true, because, why not? What could possibly be intermediate in size between the naturals and the reals? Actually, there are many such “cardinal characteristics of the continuum” - natural definitions for cardinals which are provably uncountable, and at most the cardinality of the reals, but which may be strictly between these bounds if the Continuum Hypothesis fails. I will start by giving a tour of some of these cardinals, dipping into the huge body of knowledge about provable inequalities between them and independence results. I will then present some more recent results on the robustness of some of the definitions, showing that some natural variations on the definitions leave the resulting cardinals unchanged.
Aristotelis Panagiotopoulos:
- Dynamics as obstructions to classification.
  
  One of the leading questions in many mathematical research programs is whether a certain collection of objects can be classified under some notion of equivalence using some “simple” invariants. Invariant descriptive set-theory provides a formal framework for measuring the intrinsic complexity of classification problems and for establishing such negative anti-classification results. In these lectures we will take a deep dive into this anti-classification “toolkit” and we will show how to use topological dynamics as obstruction to classification by “simple” types of invariants. We will briefly cover some classical results and then we will move to some more recent developments in relation to algebraic topology and classification by (co)homological invariants.
Rahul Santhanam:
- Introduction to Meta-Complexity. (slides)
  
  Meta-complexity is the study of the complexity of computational problems that are themselves about complexity, eg., the Minimum Circuit Size Problem (does a Boolean function $F$ given by its truth table have size at most $s$) and the problem of computing time-bounded Kolmogorov complexity. I will begin by discussing the standard notion of Kolmogorov complexity and basic results about it. I will then discuss the resource-constrained versions: defining them, mentioning basic results and informally explaining connections with important open questions in computational complexity.
- Recent Advances in Meta-Complexity. (slides)
  
  In recent years, there has been much progress on understanding meta-complexity. In the first half of my talk, I will describe some interesting new results that connect meta-complexity to learning, cryptography and proof complexity. In the second half of my talk, I will discuss a recent work of mine using meta-complexity to approach fundamental questions such as the PSPACE vs P question and the NP vs P question.
Sébastien Tavenas:
- Measuring the complexity of polynomials via algebraic circuits.
  
  Every multivariate polynomial $P(x_1,…,x_n)$ can be written as a sum of monomials, i.e. a sum of products of variables and field constants. In general, the size of such an expression is the number of monomials that have a non-zero coefficient. What happens if we add another layer of complexity, and consider sums of products of sums (of variables and field constants) expressions? Now, it becomes unclear how to prove that a given polynomial $P(x_1,…,x_n)$ does not have small expressions. We will discuss the background behind this question, the relations with standard Boolean complexity and some results from this area.