Séminaires : Séminaire Général de Logique

Equipe(s) Responsable(s)SalleAdresse
Logique Mathématique
S. Anscombe, O. Finkel, A. Khélif, A. Vignati
SG 1013 Sophie Germain

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion

Séances à suivre

Orateur(s)Titre Date DébutSalleAdresseDiffusion
+ Séances antérieures

Séances antérieures

Orateur(s)Titre Date DébutSalleAdresse
+ Mirna Džamonja Paracompactness of the box topology 11/10/2021 15:15 SG 1013 Sophie Germain
The box topology on a product of topological spaces is given by declaring as basic open sets any products of open sets of the composants of the product. It is a natural definition, but does not preserve many topological properties, notably it miserably fails to preserve compactness. However, a weakening of compactness, called paracompactness and introduced by Jean Dieudonné in 1944 for its nice behaviour in analysis, is sometimes preserved by box products. Investigating this for spaces obtained by the product of countably many factors or aleph_1 many factors with either full boxes or boxes of countable size, was a classical topic in set-theoretic topology of the 1980s or so, with important works by Mary Ellen Rudin, Kenneth Kunen, Eric van Douwen and others. In our work in progress we are, rather, interested in an unexplored territory of products with many coordinates. In particular, we consider the following question: Suppose that kappa is a cardinal such that for every lambda >= kappa, the box product {}^{<\kappa} 2^\lambda is paracompact. Is kappa a large cardinal ? (the notation means that the topology on 2^lambda is generated by boxes of size < kappa) We present some partial results and the difficulties with the consideration of the case kappa singular. This is somewhat connected with the recent works on descriptive set theory of the space 2^kappa for kappa singular. This is joint work with David Buhagiar, University of Malta.
+ Wieslaw Kubis Generic evolutions 27/09/2021 15:15
We shall present the concept of ``abstract evolution system'' which, in particular, captures the main ideas of the theory of universal homogeneous structures (Fraisse limits). Evolution systems can also be viewed as a generalization of abstract rewriting systems. We shall present an analogue of Newman's Lemma, saying that a locally confluent terminating system is confluent. Terminating evolution systems actually correspond to finite ultra-homogeneous structures.
+ Gianluca Basso Topological dynamics beyond Polish groups, and the ambitability question 20/09/2021 15:15
When $G$ is a Polish group, one way of knowing that it has nice dynamics is to show that $M(G)$, the universal minimal flow of $G$, is metrizable. For non-Polish groups, this is not the relevant dividing line: the universal minimal flow of the symmetric group of a set of cardinality $\kappa$ is the space of linear orders on $\kappa$–not a metrizable space, but still nice–, for example. In this talk, we present a set of equivalent properties of topological groups which characterize having nice dynamics. We then concentrate on an open question of Pachl and its consequences on the dynamics of topological groups. This is joint work with Andy Zucker.
+ Gabriel Conant Generically stable types and Keisler measures 16/06/2021 16:00 Contacter Sylvy Anscombe ou Alessandro Vignati
A global invariant type p is called stable if there is no witness to the order property using realizations of p, and generically stable if there is no witness to the order property using a Morley sequence of realizations of p. Hrushovski and Pillay showed that in NIP theories, a type is generically stable if and only if it is definable and finitely satisfiable in some small model. These latter properties generalize readily to Keisler measures, and so this result laid the foundation for subsequent work of Hrushovski, Pillay, and Simon on generically stable measures in NIP theories. In particular, they showed that a generically stable measure in an NIP theory is uniformly and almost surely interpreted by frequency measures, i.e., a "frequency interpretation measure". Outside of the NIP setting, this characterization no longer holds, which leads to competing options for the "right" definition of generic stability for Keisler measures in general. The focus of this talk will be on comparing and contrasting these various notions, starting with an earlier result with Gannon on "frequency interpretation types". I will then present several recent positive and negative results on the behavior of Keisler measures in arbitrary theories, as well as some examples and counterexamples. This is joint work with Gannon and Hanson.
+ Philip Welch Transfinite Computational Models and Low levels of Determinacy 09/06/2021 16:00 Contacter Sylvy Anscombe ou Alessandro Vignati
We sketch the theory of higher type Infinite Time Turing machine (ITTM) theory in the style of Kleene's type-2 recursion theory on reals, replacing ordinary turing machines by ITTM's. Besides being an interesting theory itself with many open questions, it turns out that there is a pencil and paper algorithm, i.e. a recursive isomorphism, for converting indices for such halting computations into a listing of games won by Player 1 with G_delta_sigma payoff set - in other words considering Determinacy(Sigma^0_3) for games on Cantor or Baire space. (In more formal terms the Halting Problem for this kind of computation is recursively isomorphic to a complete G-Sigma^0_3-set of integers.) One feature of this is that the ordinal where such machines crash is precisely the level in the constructible hierarchy over which strategies for such games are all definable.
+ Krzysztof Krupinski On generating ideals by additive subgroups of rings and an application to Bohr compactifications of some matrix groups 02/06/2021 16:00 Contacter Sylvy Anscombe ou Alessandro Vignati
I will present several fundamental results about generating ideals in finitely many steps inside additive groups of rings from my joint paper with T. Rzepecki. I will also mention an application to computations of definable and classical Bohr compactifications of the groups of upper unitriangular and invertible upper triangular matrices over arbitrary unital rings, based on my joint paper with J. Gismatullin and G. Jagiella. An essential role in this research is played by model-theoretic connected components of definable groups and rings. In particular, these components are used to compute the above Bohr compactifications. Regarding connected components, roughly speaking, one of our main results says that the type-definable connected component of the additive subgroup of a definable (saturated) unital ring generates an ideal in finitely many steps (and so this generated ideal is exactly the ring type-definable connected component).
+ Anush Tserunyan Backward and forward ergodic theorems along trees 26/05/2021 16:00 Contacter Silvain Rideau ou Alessandro Vignati
In the classical pointwise ergodic theorem for a probability measure preserving (pmp) transformation $T$, one takes averages of a given integrable function over the intervals $\{x, T(x), T^2(x), \hdots, T^n(x)\}$ in the forward orbit of the point $x$. In joint work with Jenna Zomback, we prove a “backward” ergodic theorem for a countable-to-one pmp $T$, where the averages are taken over arbitrary subtrees of the graph of $T$ that are rooted at $x$ and lie behind $x$ (in the direction of $T^{-1}$). Somewhat surprisingly, this theorem yields (forward) ergodic theorems for countable groups, in particular, one for pmp actions of free groups of finite rank where the averages are taken along arbitrary subtrees of the standard Cayley graph rooted at the identity. This strengthens results of Grigorchuk (1987), Nevo (1994), and Bufetov (2000).
+ Michal Doucha Descriptive complexity of Banach spaces 19/05/2021 16:00 Contacter Silvain Rideau ou Alessandro Vignati
We introduce a certain Polish space of all separable Banach spaces. The definition is in the same spirit as Grigorchuk's space of marked groups or (slightly less well known) Vershik's space of all separable complete metric spaces. We compare it with a recent different approach to topologizing the space of separable Banach spaces, by Godefroy and Saint-Raymond. Our main interest will be in the descriptive complexity of classical Banach spaces with respect to this Polish topology. We show that the separable infinite-dimensional Hilbert space is characterized as the unique Banach space whose isometry class is closed, and also as the unique Banach space whose isomorphism class is F_sigma, where the former employs the Dvoretzky theorem and the latter the solution to the homogeneous subspace problem. For p in [1,infty)-{2}, we mention that the isometry class of L^p[0,1] is G_delta-complete and the class of l^p is F_sigma,delta-complete. Also, the isometry class of c_0 is F_sigma,delta-complete. The talk will be aimed at an audience with basic knowledge of descriptive set theory and general topology, but no particular knowledge of Banach space theory. It will be based on joint work with Marek Cuth, Martin Dolezal and Ondrej Kurka.
+ Gianluca Paolini Torsion-Free Abelian Groups are Borel Complete 12/05/2021 16:00 Contacter Silvain Rideau ou Alessandro Vignati
We prove that the Borel space of torsion-free Abelian groups with domain $\omega$ is Borel complete, i.e., the isomorphism relation on this Borel space is as complicated as possible, as an isomorphism relation. This solves a long-standing open problem in descriptive set theory, which dates back to the seminal paper on Borel reducibility of Friedman and Stanley from 1989.
+ Slawomir Solecki Closed subgroups generated by generic measure preserving transformations 05/05/2021 16:00 Contacter Silvain Rideau ou Alessandro Vignati
We describe the background and outline a proof of the following theorem: for a generic measure preserving transformation $T$, the closed group generated by $T$ is not isomorphic to the topological group $L^0(\lambda, {\mathbb T})$ of all Lebesgue measurable functions from $[0,1]$ to $\mathbb T$. This result answers a question of Glasner and Weiss. The main step in the proof consists of showing that Koopman representations of ergodic boolean actions of $L^0(\lambda, {\mathbb T})$ possess a non-trivial property not shared by all unitary representations of $L^0(\lambda, {\mathbb T})$. In proving that theorem, an important role is played by a new mean ergodic theorem for ergodic boolean actions of $L^0(\lambda, {\mathbb T})$.
+ Joel Hamkins Determinacy for proper class games 14/04/2021 16:00 Contacter Silvain Rideau ou Alessandro Vignati
The principle of open determinacy for class games — two-player games of perfect information with plays of length ω, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is strictly stronger, although it is provable in the stronger theory GBC+ Pi^1_1-comprehension, a proper fragment of Kelley-Morse set theory KM.
+ Hector Pasten A framework for the DPRM property on structures 07/04/2021 16:00
A celebrated result by Davis, Putnam, Robinson and Matiyasevich shows that over the integers, listable sets are the same as Diophantine sets. There is the question of whether other interesting rings satisfy the same DPRM property and the most common setting where this problem has been considered is that of recursive rings. However, recursive rings do not seem to be the most appropriate framework: one would like to allow more general structures (not just rings) and it seems natural to allow the signature of the structure to be expanded by positive-existentially definable relations which, in general, might fail to be recursive. In this talk we will discuss the DPRM property on structures endowed with a listable presentation (rather than a recursive one) and we will present several results addressing foundational material around this notion such as uniqueness of the listable presentation, transference of the DPRM structure under interpretation, and characterization of the DPRM property in terms of p.e. bi-interpretability. As a consequence, we will obtain proofs of several folklore "facts" repeatedly claimed as results elsewhere in the literature but whose proofs are absent. Another application of the theory is that it will allow us to link various Diophantine conjectures to the question of whether or not the DPRM property holds for the field of rational numbers and for k(t) with k a finite field.
+ Marcus Tressl First order theory of semi-algebraic sets and continuous functions. 31/03/2021 16:00 ID de réunion : 825 2397 5662 Code secret : 523743
I will give an overview - and report some recent progress - on first order structures attached to collections of semi-algebraic sets and functions. Semi-algebraic here means definable in a field K that is real closed (i.e. elementary equivalent to the real field) or p-adically closed (elementary equivalent to the p-adics). For a semi-algebraic subset X of Kn let C(X) be the set of continuous semi-algebraic functions on X with values in K. There are various structures on (or derived from) C(X): We will mainly look at C(X) as a ring with pointwise operations, or as lattice ordered group with pointwise comparison (when K is real closed), as well as the lattice L(X) of closed definable subsets of X (zero sets of functions in C(X)). Key results are (in slightly paraphrased form):
(1) ( with Luck Darnière ) the ring C(X) defines true arithmetic, unless X is discrete, or K is real closed and the dimension of X is 1. This result can be used to classify the homeomorphism type of X in terms of the first order theory of the ring C(X).
(2) If K is real closed, then the theory of the lattice ordered group C(X) can be interpreted in the theory of the lattice L(X) (in a certain non-standard form), which e.g., transfers decidability results from L(X) to C(X).
(3) The remaining case in (1), when K is real closed and X is of dimension 1 is unsolved yet, but a very recent result by Deacon Linkhorn indicates a path to a model completeness result for the ring of semi-algebraic curves in a small extension of the ring language.
+ Laura Fontanella Realizability and the Axiom of Choice 24/03/2021 16:00 ID de réunion : 825 2397 5662 Code secret : 523743
Realizability aims at extracting the computational content of mathematical proofs. Introduced in 1945 by Kleene as part of a broader program in constructive mathematics, realizability has later evolved to include classical logic and even set theory. Krivine's work led to define realizability models for the theory ZF following a general technique that generalizes the method of Forcing. However realizing the full Axiom of Choice is quite problematic. After a brief presentation of Krivine's techniques, we will discuss the major obstacles for realizing the Axiom of Choice and I will present my recent joint work with Guillaume Geoffroy that led to realize weak versions of the Axiom of Choice for arbitrarily large cardinals.
+ Françoise Point On large fields of characteristic 0 endowed with a generic derivation 17/03/2021 16:00 ID de réunion : 825 2397 5662 Code secret : 523743
We first describe classes of topological large fields of characteristic 0 which can be endowed with a generic derivation. This kind of derivation recently occurred in the work of W. Johnson to describe a basis of neighbourhoods of 0 in fields of finite dp-rank (but not of finite Morley rank). We then review results we obtained with P. Cubidès on the model theory of the corresponding classes of differential fields. Finally we consider definable groups, adapting former results of A. Pillay and K. Peterzil in the o-minimal case.
+ Zoltán Vidnyánszky Bases for Borel graphs of large chromatic number 10/03/2021 16:00 ID de réunion : 825 2397 5662 Code secret : 523743
The first part of my talk will be an introduction to the field of Borel combinatorics. I will survey some of the most important results and discuss the connections to other fields. In the second part, I will talk about the structure of the collection of graphs with large Borel chromatic number, and whether it is possible to simply characterize them.
+ James Hanson A Versatile Counterexample for Invariant Types and Keisler Measures outside NIP 03/03/2021 16:00 ID de réunion : 825 2397 5662 Code secret : 523743
Global types invariant over small sets of parameters are a central concept in stability and neo-stability theory. When dealing with NIP theories in particular, it is often useful to generalize to Keisler measures, finitely additive probability measures on the Boolean algebra of definable sets. Invariant types in NIP theories behave very regularly, and these properties extend readily to invariant measures. In this talk, we will present an ornate but conceptually simple theory that is the first known counterexample to two non-NIP generalizations of statements regarding types and measures as well as the second known (correct) counterexample to another such generalization. Joint work with Gabriel Conant and Kyle Gannon.
+ Mickaël Matusinski Surreal numbers with exponential and omega-exponentiation 24/02/2021 16:00 ID de réunion : 825 2397 5662 Code secret : 523743
Introduced by Conway to evaluate partial combinatorial games, surreal numbers consist in a proper class containing "all numbers great and small". Moreover, they can be endowed with a very rich algebraic and even analytic structure, turning them into universal domains for several important theories : linearly ordered sets, ordered Abelian groups, ordered valued fields - in particular ordered generalized series fields via the omega-exponentiation -, real analytic fields and exponential fields, and more recently H-fields (an abstract version of Hardy fields due to M. Aschenbrenner and L. van den Dries). In this talk, I will introduce these fascinating objects, starting with the very basic definitions, and will give a quick overview, with a particular emphasis on exp (which extends exp on the real numbers) and the omega map (which extends the omega-exponentiation for ordinals). This will help me to subsequently present our recent contributions with A. Berarducci, S. Kuhlmann and V. Mantova concerning the notion of omega-fields (possibly with exp). One of our motivations is to clarify the link between composition and derivation for surreal numbers.
+ Elaine Pimentel A Game Model for Proofs with Costs (or: Trying to understand resource consciousness) 17/02/2021 16:00 ID de réunion : 825 2397 5662 Code secret : 523743
We look at substructural calculi from a game semantic point of view, guided by certain intuitions about resource conscious and, more specifically, cost conscious reasoning. To this aim, we start with a game, where player I defends a claim corresponding to a (single-conclusion) sequent, while player II tries to refute that claim. Branching rules for additive connectives are modeled by choices of II, while branching for multiplicative connectives leads to splitting the game into parallel subgames, all of which have to be won by player I to succeed. The game comes into full swing by adding cost labels to assumptions, and a corresponding budget. Different proofs of the same end-sequent are interpreted as more or less expensive strategies for I to defend the corresponding claim. This leads to a new kind of labelled calculus, which can be seen as a fragment of SELL (subexponential linear logic). Finally, we generalize the concept of costs in proofs by using a semiring structure, illustrate our interpretation by examples and investigate some proof-theoretical properties. The talk assumes *no prior knowledge* on games or substructural logic. Only a basic notion of sequent systems is advisable. This is a joint work with Timo Lang, Carlos Olarte and Christian G. Fermüller.
+ Rahman Mohammadpour Specializing trees of height \omega_2 with finite approximation 10/02/2021 16:00
It is well-known that under CH one can attempt to specialize trees of height ω_2 without cofinal branches using a naive forcing with countable approximations. However, one has to require more (the nonexistence of ascending paths) than the lack of cofinal branches to make sure that the naive attempt does not fail. I will discuss these possible obstacles to specialize trees of height ω_2 , and then use models as side conditions to construct a forcing notion with finite conditions, which under PFA specializes a given tree of height ω_2 without cofinal branches. If time permits, I will mention generalizations of this result to taller trees.
+ Samuel Braunfeld Cellularity and beyond 03/02/2021 16:00
Cellular structures are a class of particularly simple omega-categorical structures that yield a dividing line in many combinatorial problems concerning hereditary classes and countable structures. We will discuss where cellularity appears and its relation to the more general model-theoretic properties of mutual algebraicity and monadic stability. If time permits, we will also mention some ongoing work on monadic NIP. Much of this is joint work with Chris Laskowski.
+ Matthew de Brecht Quasi-Polish spaces as spaces of ideals, with applications to computable topology 27/01/2021 14:00
We give a brief introduction to quasi-Polish spaces, which are a class of well-behaved countably based $T_0$-spaces that generalize both Polish spaces and $\omega$-continuous domains. We then present more recent results on a characterization of quasi-Polish spaces as spaces of ideals of a transitive relation on a countable set, and investigate some applications of this characterization to computable topology.
+ Gianluca Basso Compact metrizable structures via projective Fraïssé theory 20/01/2021 16:00
The goal of projective Fraïssé theory is to approximate compact metrizable spaces via classes of finite structures and glean topological or dynamical properties of a space by relating them to combinatorial features of the associated class of structures. We will discuss general results, using the framework of compact metrizable structures, as well as applications to the study a class of one-dimensional compact metrizable spaces, that of smooth fences, and to a particular smooth fence with remarkable properties, which we call the Fraïssé fence.
+ Simon Machado Theorems of Meyer-type for approximate lattices 13/01/2021 16:00
Björklund and Hartnick recently introduced a type of approximate subgroups called approximate lattices: discrete approximate subgroups of locally compact groups with finite co-volume. Their motivation was to define a non-commutative generalisation of Meyer’s mathematical quasi-crystals (certain aperiodic subsets of Euclidean spaces with long range order). A key question asks whether Meyer’s main theorem, that asserts that quasi-crystals are projections of certain subsets of higher-dimensional lattices, holds true for all approximate lattices. I will discuss how to relate Meyer’s theorem to a consequence of Hrushovski’s stabilizer theorem and how this idea can be utilised to obtain both an extension of Meyer’s theorem to amenable groups, and a decomposition theorem à la Auslander for approximate lattices in Lie groups. The latter result will then naturally lead us to take a look at approximate lattices in semi-simple groups. While an amenable Meyer-type theorem can be proved by drawing parallels between Meyer’s and Hrushovski’s point of view, we will see how ergodic-theoretic tools from Margulis’ proof of arithmeticity and Zimmer’s proof of cocycle superrigidity lead to a partial solution in the semi-simple case.
+ Christian d'Elbée Anneaux intègres dp-minimaux 16/12/2020 16:00
Je présenterai les travaux de Yatir Halevi et moi même sur les anneaux intègres dp-minimaux. En vue de la classification des corps dp-minimaux, les anneaux intègres dp-minimaux sont proches d'être des anneaux de valuations, mais pas tout à fait. Ils sont locaux, divisés aus sens d'Akiba et tout localisé en un idéal premier non maximal est un sur-anneau de valuation. Un anneau intègre dp-minimal est un anneau de valuation si et seulement si le corps résiduel est infini ou bien le corps résiduel est fini et l'idéal maximal est principal. Je donnerai des exemples d'anneaux dp-minimaux qui ne sont pas des anneaux de valuations. Si le temps le permet, je présenterai aussi une preuve modèle-théorique d'un résultat de Echi et Khalfallah sur le spectre premier de l'anneau des nombres hyperréels bornés.
+ Andrea Vaccaro Set Theory and the Endomorphisms of the Calkin algebra 09/12/2020 16:00
Set theory induces a sharp dichotomy in the structure of the set of automorphisms of the Calkin algebra Q(H): under the Open Coloring Axiom (OCA) all the automorphisms of Q(H) are inner (Farah, 2011), whereas the Continuum Hypothesis (CH) implies that there exist uncountably many outer automorphisms of Q(H) (Phillips-Weaver, 2007). After a brief introduction on the line of research that led to these results, I'll discuss how this dichotomic behavior extends to the semigroup End(Q(H)) of unital endomorphisms of Q(H). In particular, we'll see that under OCA all unital endomorphisms of Q(H) can be, up to unitary equivalence, lifted to unital endomorphisms of B(H). This fact allows to have an extremely clean picture of End(Q(H)), and has some interesting consequences concerning the class of C*-algebras that embed into Q(H). I will also discuss how the structure of End(Q(H)) completely changes under CH.
+ Patrice Ossona de Mendez Model theory meets combinatorics 02/12/2020 16:00
The notions of first-order interpretations and transductions are the cornerstones of a bridge linking finite model theory and combinatorics in general, and graph theory in particular. I will survey some of the results and problems that emerged from this connection, including a model theoretical approach to graph sparsification and to graph limits.
+ Simon André Homogénéité faible dans les groupes virtuellement libres 25/11/2020 16:00
Il y a quelques années, Perin et Sklinos, et indépendamment Ould Houcine, ont démontré que les groupes libres sont homogènes : deux uplets d'éléments qui ont le même type sont dans la même orbite sous l'action du groupe d'automorphismes. J'expliquerai dans mon exposé que les groupes virtuellement libres, c'est-à-dire les groupes qui possèdent un sous-groupe libre d'indice fini, ont une propriété un peu plus faible : l'ensemble des uplets ayant un type donné est la réunion d'un nombre fini (uniforme) d'orbites sous l'action du groupe d'automorphismes.
+ Denis Osin A topological zero-one law and elementary equivalence of finitely generated groups 18/11/2020 16:00
The space of finitely generated marked groups, denoted by G, is a locally compact Polish space whose elements are groups with fixed finite generating sets; the topology on G is induced by the local convergence of the corresponding Caley graphs. We will discuss equivalent characterizations of closed subspaces S of G satisfying the following zero-one law: for any sentence sigma in the infinitary logic L_{\omega_1, \omega}, the set of all models of sigma in S is either meager or comeager. In particular, this zero-one law holds for certain natural spaces associated to hyperbolic groups and their generalizations. We will also discuss some open problems.
+ Jeffrey Bergfalk Set theory and strong homology: an overview 04/11/2020 16:00
Motivated by several recent advances, we will provide a research history of the main set-theoretic problems arising in the study of strong homology. We will presume no knowledge, in our audience, of the latter. The aforementioned advances close out a second major phase of research in this area, leaving just a few conspicuous last "first questions," and our aim is to provide some context for engaging them. This research centers on multidimensional combinatorial phenomena generalizing the classical theme of \emph{nontrivial coherent families indexed by $^\omega\omega$}; its progress has involved an intriguing mix of classical (forcing axioms, iterations of large cardinal length) and novel (higher-dimensional $\Delta$-systems, simplicial combinatorics) set-theoretic techniques.
+ Marcin Sabok Hyperfiniteness at Gromov boundaries 28/10/2020 16:00
I will discuss recent results establishing hyperfiniteness of equivalence relations induced by actions on Gromov boundaries of various hyperbolic spaces. This includes boundary actions of hyperbolic groups (joint work with T. Marquis) and actions of the mapping class group on boundaries of the arc graph and the curve graph (joint work with P. Przytycki)
+ Dima Sinapova Iteration, reflection, and singular cardinals 21/10/2020 17:00
There is an inherent tension between stationary reflection and the failure of the singular cardinal hypothesis (SCH). The former is a compactness type principle that follows from large cardinals. Compactness is the phenomenon where if a certain property holds for every smaller substructure of an object, then it holds for the entire object. In contrast, failure of SCH is an instance of incompactness. Two classical results of Magidor are: (1) from large cardinals it is consistent to have reflection at $\aleph_{\omega+1}$, and (2) from large cardinals it is consistent to have the failure of SCH at $\aleph_\omega$. As these principles are at odds with each other, the natural question is whether we can have both. We show the answer is yes. We describe a Prikry style iteration, and use it to force stationary reflection in the presence of not SCH. Then we obtain this situation at $\aleph_\omega$ by interleaving collapses. This is joint work with Alejandro Poveda and Assaf Rinot.
+ Tomás Ibarlucía Automorphism groups acting on Hilbert spaces without almost invariant vectors 14/10/2020 16:00
We will discuss, first, how to construct automorphisms of countable/separable saturated models (and, more interestingly, pairs of automorphisms) that act "very freely" on the structure, in a sense given by stability theory. Then we will see how to use this to show that automorphism groups of aleph_0-categorical metric structures have Kazhdan's Property (T), which roughly means that their unitary actions on Hilbert spaces do not have almost invariant vectors in non-trivial ways.
+ Luc Pelissier Entropy and Complexity Lower Bounds 07/10/2020 16:00
Finding lower bounds in complexity theory has proven to be an extremely difficult task. We analyze three proofs of lower bounds that use techniques from algebraic geometry through the lense of dynamical systems. Interpreting programs as graphings – generalizations of dynamical systems due to Damien Gaboriau that model Girard's Geometry of Interaction, we show that the three proofs share the same structure and use algebraic geometry to give a bound on the topological entropy of the system representing the program. This work, joint with Thomas Seiller, aims at proposing Geometry of Interaction derived methods to study dynamical properties of models of computation beyond Curry-Howard.
+ Luca Motto Ros Anti-classification results for Archimedean groups 30/09/2020 16:00
We study the complexity of the isomorphism relation for countable Archimedean groups, both in terms of Borel reducibility and with respect to the theory of potential classes developed by Hjorth, Kechris and Louveau. This will lead to a number of anti-classification results for such groups. We will also present similar results concerning the bi-embeddability relation over countable Archimedean groups and, if time permits, we will speak about analogous problems for countable models of certain o-minimal theories (ordered divisible abelian groups, real closed fields). Joint work with F. Calderoni, D. Marker, and A. Shani.
+ Ludovic Patey The computability-theoretic aspects of Milliken's tree theorem and applications 24/06/2020 16:00

Milliken's tree theorem states that for every countable, finitely
branching tree T with no leaves, and every finite coloring f of the
strong subtrees of height n, there is an infinite strong subtree over
which the strong subtrees of height n are monochromatic. This theorem
has several applications, among which Devlin's theorem about finite
coloring of the rationals, and a theorem about the Rado graph. In this
talk, we give a survey of the computability-theoretic aspects of these
statements seen as mathematical problems, in terms of instances and
solutions. Our main motivation is reverse mathematics. This is a joint
work with Paul-Elliot Anglès d'Auriac, Peter Cholak and Damir Dzhafarov.

+ Michał Skrzypczak Measure theory and Monadic Second-order logic over infinite trees 17/06/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

Monadic Second-order (MSO) logic is a well-studied formalism featuring many decision procedures and effective transformations. It is the fundamental logic considered in automata theory, equivalent to various other ways of defining sets of objects. In this talk, I will speak about the expressive power of MSO over infinite binary trees (i.e. free structures of two successors) - the theory from the famous Rabin's decidability result.

The goal of the talk is to survey recent results about measure properties of MSO-definable sets of infinite trees. First, I will argue that these sets are indeed measurable (which is not obvious, as there exist non-Borel sets definable in MSO). Then I will move to the question of our ability to compute the measure of the set defined by a given formula. Although the general question is still open (and seems to be demanding), I will speak about decidability results for fragments of MSO, focusing on the so-called weak-MSO.

+ Assaf Rinot Transformations of the transfinite plane 10/06/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

We study the existence of transformations of the transfinite
plane that allow to reduce Ramsey-theoretic statements concerning
uncountable Abelian groups into classic partition relations for
uncountable cardinals.

This is joint work with Jing Zhang.

+ Colin Jahel Actions of automorphism groups of Fraïssé limits on the space of linear orderings 03/06/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

In 2005, Kechris, Pestov and Todorcevic exhibited a correspondence
between combinatorial properties of structures and dynamical properties
of their automorphism groups. In 2012, Angel, Kechris and Lyons used
this correspondence to show the unique ergodicity of all the actions of
some groups. In this talk, I will give an overview of the aforementioned
results and discuss recent work generalizing results of Angel, Kechris
and Lyons.

+ Eliott Kaplan Model completeness for the differential field of transseries with exponentiation 27/05/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

 I will discuss the expansion of the differential field of logarithmic-exponential transseries by its natural exponential function. This expansion is model complete and locally o-minimal. I give an axiomatization of the theory of this expansion that is effective relative to the theory of the real exponential field. These results build on Aschenbrenner, van den Dries, and van der Hoeven's model completeness result for the differential field of transseries. My method can be adapted to show that the differential field of transseries with its restricted sine and cosine and its unrestricted exponential is also model complete and locally o-minimal.

+ Ludovic Patey TBA 27/05/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
+ Michael Hrusak Strong measure zero in Polish groups 20/05/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

We study the extent to which the Galvin-Mycielski-Solovay
characterization of strong measure zero subsets of the real line
extends to arbitrary Polish group. In particular, we show that
an abelian Polish group satisfies the GMS characterization if and only
if it is locally compact. We shall also consider the non-abelian case,
and discuss the use and existence of invariant submeasures on Polish groups.

(joint with W. Wohofsky, J. Zapletal and/or O. Zindulka)

+ Caroline Terry Speeds of hereditary properties and mutual algebricity 13/05/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs.  Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}.  Not just any function can occur as the speed of hereditary graph property.  Specifically, there are discrete ``jumps" in the possible speeds.  Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollob\'{a}s, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized.  In contrast to this, many aspects of this problem in the hypergraph setting remained unknown.  In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds.  The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. 

This is joint work with Chris Laskowski.

+ Ilijas Farah Between ultrapowers and reduced products 06/05/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

Ultrapowers and reduced powers are two popular tools for studying countable (and separable metric) structures. Once an ultrafilter on N is fixed, these constructions are functors into the category of countably saturated structures of the language of the original structure. The question of the exact 
relation between these two functors has been raised only recently by Schafhauser and Tikuisis, in the 
context of Elliott’s classification programme. Is there an ultrafilter on N such that the quotient map 
from the reduced product associated with the Fréchet filter onto the ultrapower has the right inverse? 
The answer to this question involves both model theory and set theory. 
Although these results were motivated by the study of C*-algebras, all of the results and proofs will 
be given in the context of classical (discrete) model theory.

+ Christian Rosendal Continuity of universally measurable homomorphisms 29/04/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

We show that a universally measurable homomorphism between Polish
groups is automatically continuous. Using our general analysis of
continuity of group homomorphisms, this result is used to calibrate the
strength of the existence of a discontinuous homomorphism between Polish
groups. In particular, it is shown that, modulo ZF+DC, the existence of
a discontinuous homomorphism between Polish groups implies that the
Hamming graph on {0, 1}N has finite chromatic number. This solves a
classical problem originating in JPR Christensen's work on Haar null sets.

+ Silvain Rideau-Kikuchi A model theoretic theoretic account of the tilting equivalence 22/04/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

Generalizing work of Krasner and Fontaine-Wintenberger on the isomorphism of absolute Galois groups between a mixed characteristic perfectoid field K and its charactersitic p tilt K^flat = prolim_{x -> x^p} K, Scholze introduced a notion of perfectoid adic space and proved an equivalence of category between perfectoid adic spaces over K and over K^flat. The goal of this talk will be to give a model theoretic translation of these results. We will show that, in a well chosen continuous structure, K and K^flat are bi-interpretable and that this immediately yields an equivalence of categories between type spaces over K and K^flat. We will then explain how these result relate to Scholze's results in adic geometry.

This is joint work with Tom Scanlon and Pierre Simon

+ Pablo Cubides Kovacsics Pairs and pro-definability of type spaces 15/04/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
Let T be a complete L-theory and M be a model of T. Let x be a tuple of variables and S_x(M) be the space of types over M with free variables x. In this talk we will be interested in the subset S_x^def(M) of S_x(M) of definable types. We will show that for various classical first order theories, including o-minimal expansions of divisible abelian groups, Presburger arithmetic, p-adically closed fields, real closed and algebraically closed valued fields and closed ordered differential fields, the space S_x^def(M)$ is pro-definable, i.e., a projective limit of definable sets.
Our general strategy consists in studying the class of stably embedded pairs of models of the T. Pro-definability is obtained by showing that such class is elementary in the language of pairs.
This is joint work with Jinhe Ye.
+ Laurent Bartholdi Problèmes de domino sur les groupes 06/04/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge

Soit G un groupe, fixé une fois pour toutes. On s'intéresse aux
sous-décalages sur G de type fini: ce sont les sous-ensembles fermés
G-invariants de {1,...,d}^G définis par un ensemble fini de mots
interdits. Dualement, ce sont aussi les G-algèbres booléennes de
présentation finie.

Plus précisément, on s'intéresse aux problèmes de décision suivants:
est-il décidable, à partir d'une liste de mots interdits, si le
sous-décalage associé est non-vide? ou même mieux s'il contient un
ouvert donné (spécifié par des valeurs sur un ensemble fini de
coordonnées)? Dualement, l'algèbre associée est-elle triviale? ou
a-t-elle problème du mot résoluble?

Ces problèmes ont été surtout considérés pour G=ℤ^2, auquel cas on parle
de «pavages de Wang»; ces deux problèmes sont indécidables.

Selon une conjecture de Jeandel, ces problèmes sont algorithmiquement
résolubles seulement si G a un sous-groupe libre d'indice fini. Je
décrirai l'état du problème, et ajouterai une contribution, obtenue en
collaboration avec Ville Salo: pour le groupe de
l'«allumeur de réverbères» G=ℤ/2≀ℤ.

Ce groupe est important car il apparaît à la frontière entre "arbre"
(groupes libres) et "plan" (Z^2). Nous montrons que son problème de
domino est indécidable.

+ Pablo Cubides Kovacsics Séance-annulée - TBA 30/03/2020 15:15 2015 Sophie Germain
+ Konstantin Slutsky Séance annulée - Smooth orbit equivalence of free Borel $R^d$ actions. 30/03/2020 16:00 https://bigbluebutton.imj-prg.fr/b/sil-gwg-gge
Smooth Orbit Equivalence (SOE) is an orbit equivalence relation between free $R^d$ flows which acts as diffeomorphism between orbits.  This concept originated in ergodic theory of $R$ flows under the name of time change equivalence, where it is closely connected with the concept of Kakutani equivalence of induced transformations.  When viewed from the ergodic theoretical viewpoint, SOE has a rich structure in dimension one, but, as discovered by Rudolph, all ergodic measure preserving $R^d$ flows, $d > 1$, are SOE.  
Miller and Rosendal initiated the study of this concept from the point of view of descriptive set theory, where phase spaces of flows aren't endowed with any measures.  This significantly enlarges the class of potential orbit equivalences, and they proved that all non trivial free Borel $R$ flows are SOE.  They posed a question of whether the same remains to be true in dimension $d>1$.  In this talk we answer their question in the affirmative, and show that all non trivial Borel $R^d$ flows are SOE.
+ Luc Pelissier Séance annulée - TBA 23/03/2020 15:15 2015 Sophie Germain
+ Christian Espindola Séance annulée - TBA 16/03/2020 15:15 2015 Sophie Germain
+ Amador Martin-Pizarro Asymptotic Combinatorics, Stability and Ultrafilters 09/03/2020 15:15 2015 Sophie Germain

A finite subset A of a group G is said to have doubling K if the set A\cdot A consisting of products a\cdot b, with a and b in A, has size at most K|A|. Extreme examples of sets with small doubling are cosets of (finite) subgroups.

Theorems of Freiman-Ruzsa type assert that sets with small doubling are "not too far" from being subgroups. Freiman's original theorem asserts that a finite subset of the integers with small doubling is efficiently contained in a generalized arithmetic progression.  A version of this result for abelian groups of bounded exponent was given by Ruzsa:  a finite subset with small doubling K of an abelian group G of exponent r is contained in a subgroupH of G of size bounded by K, r and |A| (but the bound he exhibited is exponential). A natural reformulation of the problem is the polynomial Freiman-Ruzsa conjecture, one of the central open problems in additive combinatorics, which aims to find polynomial bounds (in K) so that any subset A of small doubling K in an infinite-dimensional vector space over F_2 can be covered by finitely many translates of some subspace, whose size is commensurable to the size of A. Improvements of this result have been subsequently obtained by many authors for arbitrary (possibly infinite and non-abelian) groups.

Motivated by work of  E. Hrushovski, we will present on-going work with D. Palacin (Freiburg) and J. Wolf (Cambridge) of Freiman-Ruzsa type under stability, an assumption of model-theoretic nature.

+ Matteo Viale Tameness for Set Theory 02/03/2020 15:15 2015 Sophie Germain

We show that (assuming large cardinals) set theory is a tractable (and we dare to say tame) 
first order theory when formalized in a first order signature with natural predicate symbols for the basic 
definable concepts of second and third order arithmetic, and appealing
to the model-theoretic notions of model completeness and model companionship. 

Specifically we develop a general framework linking 
generic absoluteness results to model companionship and
show that (with the required care in details) 
a $\Pi_2$-property formalized in an appropriate language for second or third order number theory 
is forcible from some 
$T\supseteq\ZFC+$\emph{large cardinals}
if and only if it is consistent with the universal fragment of $T$
if and only if it is realized in the model companion of $T$.

+ Gareth Jones Powers are easy to avoid 24/02/2020 16:15 8029 Sophie Germain

Suppose that a set is definable in the expansion of the real
field by restricted analytic functions, and is also definable in the
expansion of the real field by the restricted exponential function
together with all real power functions. Then the set is definable
using just the restricted exponential function. So additional
exponents can be avoided. I will discuss the general result behind
this, and how it can be seen as a polynomially bounded version of an
old conjecture of van den Dries and Miller. This is joint work with
Olivier Le Gal.

+ Nick Ramsey Around exact saturation 17/02/2020 15:15 2015 Sophie Germain
Given a singular cardinal κ and a complete theory T, we say T has exact saturation at κ if there is a κ-saturated model of T that is not κ+-saturated. Stable theories and the random graph have exact saturation at every singular cardinal, while a dense linear order has exact saturation at no singular cardinal–accordingly, failure of exact saturation may be regarded as an avatar of linear order and one might attempt to classify theories according to whether they do or do not have exact saturation. We will describe recent work, joint with Itay Kaplan and Saharon Shelah, which offers several variations on this theme.
+ Alessandro Andretta A descriptive view of the density point property in measure theory 03/02/2020 15:15 2015 Sophie Germain

I plan to give an overview of some of the work on descriptive set theory related to the Lebesgue density theorem.
Part of this work is joint with R. Camerlo and C. Costantini, part of it is still unpublished.

+ François Le Maître Actions ultrahomogènes sur le graphe aléatoire 20/01/2020 15:15 2015 Sophie Germain

Le graphe aléatoire est l'unique graphe dénombrable infini universel (contenant tous les graphes finis comme sous-graphes) et tel que l'action de son groupe d'automorphisme soit ultrahomogène : tout isomorphisme partiel entre des sous-graphes finis s'étend en un automorphisme global du graphe. Il est naturel de se demander quels sont les groupes dénombrables admettant eux-même une action ultrahomogène sur le graphe aléatoire, autrement dit : quels sont les sous-groupes dénombrables denses du groupe d'automorphisme du graphe aléatoire ? Dans cet exposé, on donnera de nouveaux exemples de tels groupes (notamment les groupes de surface), obtenus dans un travail en commun avec Pierre Fima, Julien Melleray et Soyoung Moon.

+ Philipp Schlicht Oligomorphic groups are essentially countable 09/12/2019 15:15 2015 Sophie Germain
Model theoretic properties of a countable structure are closely connected with properties of its automorphism group. For instance, the automorphism groups of ω-categorical structures on N are precisely the oligomorphic closed subgroups of Sym(N) (a permutation group is oligomorphic if for each k there are only finitely many k-orbits). We study the complexity of topological isomorphism of oligomorphic closed subgroups of Sym(N) in the setting of Borel reducibility. Previous work of Kechris, Nies and Tent, and independently Rosendal and Zielinski, showed that this equivalence relation is below graph isomorphism. We show that it is below a Borel equivalence relation with countable equivalence classes. This is joint work with Andre Nies and Katrin Tent. 
+ Andreas Hallback Locally Roelcke precompact groups and continuous logic 02/12/2019 15:15 2015 Sophie Germain

The topic of this talk lies at the intersection of continuous logic and Polish group theory. Inspired by a result of Ben-Yaacov, Rosendal and Tsankov characterising the Roelcke precompact Polish groups as automorphism groups of separably categorical metric structures, we give a characterisation of the locally Roelcke precompact Polish groups, using concepts from continuous model theory. If time permits, we will see how this result applies to the so-called Urysohn diversity - a hypergraph version of metric spaces introduced recently by Bryant, Nies and Tupper. We will give brief introductions to all subjects involved, but hope the audience is somewhat familiar with continuous logic.

+ Victor Vianu Analysis of data-driven workflows 25/11/2019 15:15 2015 Sophie Germain
Software systems centered around databases have become pervasive in a wide variety of applications, including health-care management, e-commerce, business processes, scientific workflows, and e-government. Such applications support complex workflows involving numerous interacting actors, whence the critical need for various analysis tools. Unlike arbitrary software systems, data-driven applications are increasingly specified using high-level logic-based tools, which greatly facilitates the analysis task. This new opportunity has given rise to a flourishing research area at the intersection of databases and computer-aided verification, in both academia and industry. This talk will present an overview of recent research in this area, carried out with collaborators at UC San Diego, INRIA, CNRS and ENS.
+ Matteo Mio Towards a Proof Theory of Probabilistic Logics 18/11/2019 15:15 2015 Sophie Germain

Probabilistic Logics are formal languages designed to express properties of probabilistic programs. For most probabilistic logics several key problems are still open. One of such problems is to design convenient analytical proof systems in the style
 of Gentzen sequent calculus. This is practically important in order to simplify the task of proof search: the CUT-elimination theorem greatly reduces the search space. In this talk I will present some recent developments in this direction.

+ Asaf Karaglia Countable unions of countable sets, their power sets, and the axiom of choice 04/11/2019 15:15 2015 Sophie Germain

The union of countably many countable sets is countable, assuming the axiom of choice, and its power set is finite or the same size as the real numbers. But what happens without the axiom of choice? We will go over the basic results and slowly builds towards the theorem of D.B. Morris: There is no bound on how many subsets a countable union of countable sets can have.

(Only rudimentary knowledge in set theory is needed.)

+ Andrew Zucker Weak amalgamation versus amalgamation 28/10/2019 15:15 2015 Sophie Germain

Fraisse classes are those classes F of finite structures satisfying the Hereditary Property (HP), the Joint Embedding Property (JEP), and the Amalgamation Property (AP). The JEP allows one to build some countably infinite structure K whose age (the collection of finite structures which embed into K) is the class F that we started with. If AP also holds, then there is a canonical such K which we denote K_F, the Fraisse limit of the class. One can interpret this fact dynamically by considering the action of the group S_\infty on the space X_F of countable structures whose age is contained in F. One can give X_F a natural Polish topology, and the theorem of Fraisse is precisely the fact that this action has a comeager orbit. However, Ivanov, and later Kechris-Rosendal, isolated a strictly weaker property, the Weak Amalgamation Property (WAP), which also guarantees that the space X_F has a comeager orbit. This gives rise to a natural question: can we detect the difference between AP and WAP from the dynamical point of view? This talk will discuss an affirmative answer, linking these amalgamation properties to the dynamical notion of a highly proximal extension.

+ Sylvy Anscombe Axiomatizing denseness in real and p-adic closures 21/10/2019 15:15 2015 Sophie Germain

The real/p-adic closures of an ordered/p-valued field need not be complete. Conversely, one may wonder when an ordered/p-valued field is dense in its real/p-adic closures.

We study the property of a field that it is dense in all its real/p-adic closures. We examine when this property is elementary in the language of rings. It is not always elementary, but for fields with finite Pythagoras/p Pythagoras numbers, it is so. In particular we show that this property holds for models of the theory of algebraic fields of characteristic zero. This essentially includes all previously known examples. This is joint work with Philip Dittmann and Arno Fehm.

+ Konstantin Slutsky Orbit Equivalence Relations of Borel Flows 14/10/2019 15:15 2015 Sophie Germain
We present an overview of the theory of orbit equivalence relations of Borel flows, (i.e. free Borel actions of the Euclidean space). While more familiar in the framework of countable group actions, orbit equivalence is an important tool in understanding the structure of $\mathbb{R}^n$ actions just as well.  We will survey a number of related results including:
- the classification of Borel flows up to Lebesgue Orbit Equivalence
  (which can be viewed as the analog of Dougherty--Jackson--Kechris classification of hyperfinite equivalence relations);
- connections of this classification to Rudolph's theorem about regular cross sections;
- Topological Orbit Equivalence, including the Miller--Rosendal theorem on time-change equivalence.
+ Alex Berenstein Randomizations and groups 30/09/2019 15:15 2015 Sophie Germain
Randomizations were introduced by Keisler and Ben Yaacov and they can be understood intuitively as random variables with values in M. In this talk we will give a brief introduction to the subject and study two kinds of groups that appear naturally in the construction:
1. When M is a group, the randomization inherits a natural pointwise group operations that inherits many properties from M: being abelian, definably nilpotent, etc. We show (joint work with Muñoz) that when T is stable its randomization is always connected group.
2. The group of isometries of these structures have been characterized and studied by Ibarlucía. They can be understood in terms of the group of automorphisms of M. We will discuss several topologies that arise naturally in this group and prove (joint work with Zamora) how some dynamical properties of Aut(M) transfer to the group of isometries of its Borel randomization.
+ Jörg Brendle, University of Kobe, Japan Cardinal invariants, small and large 16/09/2019 15:15

{\em Cardinal invariants of the continuum} are cardinal numbers describing the combinatorial structure of the  real numbers (the Cantor space $2^\omega$ or the Baire space $\omega^\omega$) and typically taking values between the first uncountable cardinal $\aleph_1$ and the cardinality of the continuum $\mathfrak c$. An example is the unbounding number $\mathfrak b$, the smallest size of a family of functions in $\omega^\omega$unbounded in the eventual dominating ordering. Such cardinal invariants have many applications in areas like general topology, group theory, real analysis, etc. 

While cardinal invariants of the continuum have been investigated intensively for decades, more recently people have started to look at the higher Cantor space $2^\kappa$ and the higher Baire space $\kappa^\kappa$, where $\kappa$ is an uncountable regular cardinal, and redefined analogous cardinals, called {\em higher cardinal invariants},in this context. Many results known for $\omega$ carry over to $\kappa$, in particular in the case when $\kappa$ is a large cardinal. However, there are also several interesting differences between the classical case and higher cardinalinvariants.

I will give a survey on cardinal invariants, starting with the classical case, and then moving to higher invariants.

+ David Evans Higher amalgamation in measurable structures 20/05/2019 15:10
Measurable structures were introduced by Macpherson and Steinhorn in 2008. Their definition abstracts certain properties of pseudofinite fields (following work of Chatzidakis, van den Dries and Macintyre) and has as a consequence that MS-measurable structures are supersimple of finite rank.

We give a higher amalgamation property which holds in MS-measurable structures (and more general contexts) which is a straightforward consequence of an infinitary formulation due to Towsner of the Hypergraph Removal Lemma.

It is an open question whether omega-categorical MS-measurable structures are necessarily one-based. Hrushovski constructions could potentially give counterexamples, but it is not known whether these can be MS-measurable. However, as a consequence of the higher amalgamation result, we can at least give an example of an omega-categorical supersimple Hrushovski construction which is not MS-measurable.

+ Raphaël Carroy Le plongement topologique et la réduction continue sur la première classe de Baire 13/05/2019 15:10
Une fonction entre espaces polonais de dimension zéro est de première classe de Baire lorsqu'elle est ponctuellement la limite d'une suite de fonctions continues. Cet exposé sera centré sur deux quasi-ordres entre fonctions de première classe de Baire: le plongement topologique et la réduction continue.

Un plongement topologique entre espaces est une injection continue dont la fonction inverse est également continue. Un plongement topologique d'une fonction $f$ dans une fonction $g$ est une paire $(a,b)$ de plongements topologiques vérifiant l'équation $b \circ f = g \circ a$. Une réduction continue de $f$ à $g$ est une paire $(a,b)$ de fonctions continues vérifiant l'équation $f = b \circ g \circ a$.

On parlera de la complexité de ces deux quasi-ordres: on identifiera des sous-classes de fonctions sur lesquelles ils sont des bons-quasi-ordres, c'est à dire bien fondés et sans antichaînes infinies. On verra également que le plongement topologique n'est pas toujours un bon-quasi-ordre, dans certains cas il est en fait complet pour les quasi-ordres analytiques.
+ Alexis Saurin De la descente infinie à la programmation avec des types (co)inductifs 15/04/2019 15:10
La logique de la programmation s'est développée depuis la mise en évidence des liens étroits qu'entretiennent théorie de la démonstration et théorie de la programmation. La correspondance, dite de Curry-Howard, entre
1) formules logiques et types de données
2) preuves et programmes
3) élimination des coupures (ou normalisation de preuve) et exécution d'un programme
a stimulé une intense activité visant à comprendre le contenu logique des structures de programmation et le contenu calculatoire des formes du raisonnement ou des axiomes logico-mathématiques et a renouvelé les perspectives sur la programmation comme sur la théorie de la démonstration.

Dans cet exposé, on s'intéressera à diverses formes de raisonnements par induction, de la récurrence usuelle à la descente infinie, et aux systèmes de preuves qui les formalisent. Je considérerai notamment des logiques à points fixes (dérivées du mu-calcul, qui permettent d'exprimer aussi bien des enoncés inductifs que coinductifs), dans lesquelles j'étudierai des systèmes de preuves non bien-fondés où les dérivations sont des arbres potentiellement infinis (éventuellement réguliers). Je présenterai les principaux résultats de la théorie de la démonstration infinitaire (en particulier l'élimination des coupures), ses relations avec les preuves finitaires ainsi que des perspectives d'application à la programmation.
+ Anton Freund Collapsing large ordinals 08/04/2019 15:10
This talk discusses the power of "almost" order preserving collapsing functions, which map large ordinals (uncountable resp. non-recursive) to smaller ones (countable resp. recursive). More precisely, I will consider collapsing functions in the context of dilators (J.-Y. Girard): Let $D$ be a dilator, i.e. a particularly uniform function from ordinals to ordinals. It can happen that we have $D(\alpha)>\alpha$ for every ordinal $\alpha$, so that $D$ has no fixed-point. The best we can expect is a collapsing function $D(\alpha)\rightarrow\alpha$ that is almost order preserving, in a sense that will be made precise in the talk. If such a function exists, then $\alpha$ is called a Bachmann-Howard fixed-point of $D$. I will show that the following holds over a weak base theory: The statement that "every dilator has a Bachmann-Howard fixed-point" is equivalent to the existence of admissible sets, and hence to $\Pi^1_1$-comprehension (full details can be found in arXiv:1809.06759).
+ Françoise Point Expansions de corps dp-minimaux avec une derivee et applications aux theories de paires denses de corps 25/03/2019 15:10
L'etude des corps topologiques differentiels est traditionnellement divisee en deux branches, l'une traite le cas ou il y a une interaction (forte) entre la derivee et la topologie et l'autre ou le comportement de la derivee sera generique. Nous nous placons dans ce dernier cas. Sous certaines conditions sur une theorie modele-complete de corps topologiques, on peut axiomatiser la theorie T^*_D de la classe des expansions differentielles existentiellement closes.

Le but de l'expose est d'expliquer quelques resultats de transferts entre T et T^*_D et de montrer comment les appliquer aux theories de paires denses de modeles de T.

Il s'agit d'un travail en commun et en cours avec Pablo Cubides (Dresden).
+ Thomas Seiller Des preuves aux programmes, aux systèmes dynamiques. Perspectives géométriques en complexité algorithmique 18/03/2019 15:10
La question de la séparation des classes de complexité fait actuellement face à un manque cruel de méthodes. En effet, de nombreux résultats, appelés barrières, démontrent que les méthodes de preuve connues ne permettront pas de répondre aux questions ouvertes principales. Le principal programme de recherche qui pourrait circonvenir aux barrières est le programme de complexité géométrique de K. Mulmuley. Celui-ci propose de montrer des résultats de séparation via des techniques de géométrie algébrique, et a été introduit après l'obtention d'un résultat de bornes inférieures une variante algébrique de PRAMs, un modèle de machines parallèles ad-hoc.

Cet exposé expliquera comment certaines méthodes récentes venant de la logique permettent de proposer une nouvelle approche à la question de la séparation. Basée sur une interpretation dynamique des programmes, celle-ci suggère une correspondance entre l'expressivité des modèles de calcul étudiés et certains invariants venant de théorie ergodique. Je présenterai également un travail en collaboration avec L. Pellissier, qui a consisté à relire la preuve de séparation ayant inspiré le programme de complexité géométrique via ce nouveau point de vue, faisant apparaitre le rôle de l'entropie topologique des systèmes dynamiques associés aux machines. Au-delà de renforcer l'intuition d'une correspondance entre classes de complexité et certaines classes de systèmes dynamiques, cette abstraction du résultat nous permet également de renforcer le résultat de séparation pour montrer que le problème maxflow (problème complet pour la classe P) n'est pas calculable efficacement par une machine parallèle travaillant avec des entiers.
+ Martin Bays Isolation, compression schemes, and density of compressibility 11/03/2019 15:10
In model theory, various notions of isolation - ways in which the full information of a type may be determined by a fragment of it - have been important tools for the analysis and classification of models of a theory. Meanwhile, much has been written in machine learning theory on sample compression schemes - ways to code information on a concept in a bounded part.

These related ideas came together in work of Chernikov and Simon on NIP and distal theories, where they found in particular that a theory is distal precisely when every type satisfies a certain isolation notion, termed "compressibility". A model-theoretically natural question to ask of such an isolation notion is whether isolated types are dense in the natural topological space of types.

Meanwhile, a recent result of Chen, Cheng, and Tang provides a strong form of compression scheme for a finite concept class, bounded in terms of its VC dimension.

In work joint with Itay Kaplan and Pierre Simon, we give a certain generalisation of this last result to infinite concept classes, and use it to obtain density of compressible types in countable NIP theories.
+ Joan Bagaria Symmetry and Self-Similarity in the Higher Infinite 04/03/2019 15:10
The Higher Infinite is the realm of the Large Cardinals, namely very large infinite cardinal numbers with strong combinatorial properties and whose existence cannot be proved from the standard Zermelo-Fraenkel axioms of set theory with Choice (ZFC). Large cardinal axioms of set theory assert the existence of such cardinals, which form a hierarchy that measures the consistency strength of mathematical theories. In this talk we will present some results, some old as well as some recent ones, that point to a unified view of the large cardinal hierarchy in terms of symmetry and self-similarity of the set-theoretic universe.
+ Hector Pasten Diophantine sets of number fields and their rings of integers --- à 16h en salle 1016 25/02/2019 16:00
A subset of a ring is diophantine if it is positive existentially definable in the language of rings. In number fields or in their rings of integers, every diophantine set is listable (i.e. recursively enumerable) and one can ask whether every listable set is diophantine. For instance, a classical theorem of Davis, Matiyasevic, Putnam, and Robinson shows that for the usual integers Z the answer is positive. I will discuss some general conjectures and some partial results suggesting that in the number field case not every listable set is diophantine, while in the case of rings of integers every listable set should be diophantine.

+ Benjamin Siskind Meta-iteration trees and mouse pairs 18/02/2019 15:10
The fundamental objects of study in inner model theory are iterable premice---fine-structual models of set theory which have winning strategies in certain iteration games. In the standard iteration game, two players work to produce an iterate N of a premouse M via a tree of iterated ultrapowers called a normal iteration tree. In a variant game, players produce an iterate N not via a single iteration tree but via a linear stack of normal trees. Recent work has revealed connections between these games, which have various applications in inner model theory. The key framework for understanding these connections is the theory of meta-iteration trees: iteration trees of iteration trees. Using this framework, we show that any nice winning strategy S in the standard game extends to a winning strategy S* in the variant game. Moreover, every iterate N obtainable via a play by S* in the variant game is actually obtainable via a play by the original strategy S. This is joint work with John Steel.
+ Paul-André Melliès Jeux de gabarit: un modèle homotopique et interactif de la logique linéaire différentielle 04/02/2019 15:10
La sémantique des jeux permet de décrire toute formule logique comme un jeu de dialogue et toute démonstration comme une stratégie interactive. Dans cet exposé introductif, j'expliquerai comment la notion de jeu de gabarit est née du désir de mieux comprendre la structure algébrique et combinatoire en espace et en temps de la sémantique des jeux. Mon exposé sera organisé en trois parties. J'expliquerai tout d'abord ce qu'est un modèle catégorique de la logique linéaire différentielle formulée par Thomas Ehrhard. Je décrirai ensuite le modèle des distributeurs et espèces généralisées formulé il y a dix ans par Marcelo Fiore, Nicola Gambino, Martin Hyland and Glynn Winskel, et les liens que ce modèle entretient avec la notion d'opérade en topologie algébrique. Je conclurai en décrivant le modèle des jeux de gabarit, et en expliquant les raisons pour lesquelles on doit faire interagir les démonstrations logiques modulo une notion d'homotopie, formulée dans le cadre des catégories modèles de Quillen.
+ Esther Elbaz Structures dont l'anneau de Grothendieck est $\mathbb{Z}/N\mathbb{Z}$ 28/01/2019 15:10
Les anneaux de Grothendieck ont été introduits en théorie des modèles au début des années 2000. Ils sont une généralisation de la notion d'anneau de Grothendieck connue en géométrie algébrique. Il existe un parrallèle entre mes propriétés combinatoires d'une structure et les propriétés algébriques de son anneau de Grothendieck. Ces anneaux apparaissent également en intégration motivique, où ils sont utilisés pour exprimer de manière uniforme les formules de certaines fonctions de comptage.
On peut se demander quels anneaux peuvent apparaître comme anneaux de Grothendieck. On ne savait pas jusque récemment, s'il en existait de finis.
Dans cet exposé, nous montrerons que pour tout nombre entier $N$, nous allons construire une théorie dont tous les modèles admettent $\mathbbZ/N \mathbbZ$ comme anneau de Grothendieck.
+ Paola d'Aquino Roots of exponential polynomials 21/01/2019 15:10
Zilber identifies a new class of exponential fields (pseudo-exponential fields), and proves a categoricity result for every uncountable cardinality. He conjectures that the classical complex exponential field is the unique model of power continuum. Some of the axioms of Zilber have a geometrical nature and they guarantee solvability of systems of exponential equations over the field. In the last 15 years much attention has been given to extend classical results for the complex exponential field to the pseudo-exponential fields, and vice versa much effort has been put in proving for the complex field properties of solutions of exponential polynomials which follow from the axioms of Zilber. Analytic methods have been substituted by algebraic and geometrical arguments. I will review some of the first results on this and I will present more recent ones obtained in collaboration with A. Fornasiero and G. Terzo

+ Alessandro Vignati Logic and Cech-Stone remainders 14/01/2019 15:10
We study the properties of Cech-Stone remainder spaces, spaces of the form beta X minus X for a locally compact X where beta X denotes the Cech-Stone compactification of X. We focus on how logic interacts with the study of these objects. We approach such spaces both model theoretically, by looking at the continuous model theory of the C*-algebra of complex valued functions on beta X minus X, and set theoretically, by arguing that their homeomorphism structure depends on the axioms in play.
+ Juliette Kennedy On Extended Constructibility 10/12/2018 15:10
If we replace first order logic by second order logic in the original definition of Gödel’s inner model L, we obtain HOD (result due to Myhill-Scott). In this talk after giving some historical background we consider inner models that arise if we replace first order logic by a logic that has some, but not all, of the strength of second order logic. Typical examples are the extensions of first order logic by generalized quantifiers, such as the Magidor-Malitz quantifier ([21]), the cofinality quantifier ([32]), or stationary logic ([6]). Our first set of results show that both L and HOD manifest some amount of robustness in the sense that they are not very sensitive to the choice of the underlying logic. Our second set of results shows that the cofinality quantifier gives rise to a new robust inner model between L and HOD. We show, among other things, that assuming a proper class of Woodin cardinals the regular cardinals above \aleph_1 of V are weakly compact in the inner model arising from the cofinality quantifier and the theory of that model is (set) forcing absolute and independent of the cofinality in question.
+ Hugo Herbelin Calculer avec le théorème de complétude de Gödel 03/12/2018 15:10
Dans un premier temps, nous donnerons une analyse du contenu calculatoire de la preuve de Henkin du théorème de complétude (dans le cas d'une théorie récursivement énumérable).

Dans un deuxième temps, on s'intéressera à la traduction de forcing de l'énoncé de complétude pour s'apercevoir qu'on obtient alors un énoncé de complétude vis à vis des modèles de Kripke. En ré-interprétant la preuve standard de complétude vis à vis des modèles de Kripke en style direct (dans le même sens où la logique classique est un « style direct » pour raisonner intuitionnistiquement au travers des traductions négatives de Kolmogorov-Gödel-Gentzen), on obtiendra une preuve originale et calculatoire très simple du théorème de complétude... mais qui utilise une allocation mémoire !
+ Hadrien Batmalle Forcing, réalisabilité classique et propriétés de préservation 26/11/2018 15:10
La réalisabilité classique est une technique d'interprétation des énoncés d'une théorie par des programmes. Elle permet de construire des modèles et apparaît comme une généralisation du forcing. Si l'interprétation de théorèmes par des programmes a un intérêt évident en informatique, l'étude des modèles de ZF obtenus par réalisabilité classique est aussi intéressante en soi: en effet, sauf dans les cas dégénérés, ces modèles sont très différents des modèles de forcing; par exemple ils ne conservent pas les ordinaux. Cela permet d'exhiber des propriétés pathologiques qu'on ne savait pas obtenir précédemment (on a donc un outil supplémentaire pour les preuves d'indépendance) mais présente aussi de nouvelles difficultés. En particulier, si on sait bien souvent en forcing quels sont les critères que doit vérifier la structure des conditions pour obtenir telle ou telle propriété dans le nouveau modèle, la réalisabilité est, pour le moment, beaucoup plus difficile à aborder. On présentera ici quelques
techniques récentes de réalisabilité classique à rapprocher de techniques bien connues en forcing: l'opérateur de bar-récursion, qui joue un rôle analogue aux ensembles de conditions omega-clos (Krivine 2014) et un nouveau résultat de transfert de propriétés du modèle de départ qui est utilisé dans les mêmes situations que des critères de type conditions d'antichaîne. On appliquera ce dernier résultat à la construction de modèles de réalisabilité pour la négation du choix dénombrable et la négation de l'hypothèse du continu, et donc de programmes réalisant ces énoncés.
+ Guillaume Malod Les séries d'arbres et la complexité algébrique 19/11/2018 15:10
Un résultat de Nisan de 1991 donne une caractérisation exacte de la complexité de calcul d'un polynôme non-commutatif par un modèle appelé branching program, via les rangs de certaines matrices. Fijalkow, Lagarde, Ohlmann et Serre ont récemment remarqué que ces résultats étaient en fait des cas particuliers de théorèmes sur les séries formelles de mots et d'arbres et ont cherché à les exploiter ceux-ci pour les appliquer à la complexité algébrique.
J'essaierai de faire une présentation synthétique de ces différents résultats.
+ Frank Wagner Anneaux et groupes dimensionnels 12/11/2018 15:10
Je définirai une notion générale de dimension sur les ensembles interprétables d'une structure, et j'analyserai les anneaux et groupes qui peuvent être munis d'une telle dimension.
+ Thomas Ehrhard Sur la sémantique des langages de programmation probabilistes 05/11/2018 15:10
La sémantique dénotationnelle, introduite par Scott et Strachey à la fin des années 1960, consiste à interpréter les programmes par des fonctions définies sur des "domaines" qui sont le plus souvent des ensembles partiellement ordonnés dans lesquels, intuitivement, un élément est d'autant plus grand qu'il est plus défini. On présentera une sémantique dénotationnelle des programmes probabilistes basée sur les "espaces cohérents probabilistes" dans laquelle les programmes sont interprétés par des fonctions analytiques dont toutes les dérivées sont positives, on donnera des exemples et on présentera diverses propriétés de ce modèle (adéquation, pleine abstraction etc).
+ Frank Benoist Ingrédients modèle-théoriques dans la preuve de la conjecture de Mordell-Lang 29/10/2018 15:10
La preuve de la conjecture de Mordell-Lang pour les corps de fonctions par Hrushovski en 1996 constitue un exemple marquant d'application des méthodes de la théorie des modèles à la géométrie algébrique. Depuis, dans un travail commun avec Elisabeth Bouscaren et Anand Pillay, nous avons donné une preuve, se voulant plus abordable, de ce résultat, par réduction à la conjecture (démontrée) de Manin-Mumford. J'expliquerai les relations entre ces deux énoncés et présenterai les outils et méthodes de théorie des modèles qui interviennent dans la preuve. L'exposé se veut accessible aux non-spécialistes.

+ David Aspero The special $\aleph_2$-Aronszajn tree property and GCH 15/10/2018 15:10
Assuming the existence of a weakly compact cardinal, we build a forcing extension in which GCH holds and every $\aleph_2$-Aronszajn tree is special. This answers a well-known question from the 1970's. I will present the proof of this theorem, with as many details as possible. This is joint work with Mohammad Golshani.

+ Jouko Vaananen An invitation to dependence logic 08/10/2018 15:10
I will give an introduction to dependence logic and to the team semantics on which it rests. Dependence logic is an inquiry into the first order and algorithmic properties of dependence and independence relations in mathematics, statistics and computer science. I will discuss connections to model theory, database theory, quantum physics, social choice and set theory. It is perhaps surprising that the opposite of dependence is not independence, but rather anonymity or privacy, extending the investigation into another notoriously important field.
+ Alessandro Vignati L'exposé est reporté à une date ultérieure - Uniform Roe algebras and rigidity, part II 24/09/2018 15:10
This talk is the second part of Farah's talk from two weeks ago. From a coarse metric space X one associates a C*-algebra known as the Uniform Roe algebra of X. This algebra has a canonical quotient called the Uniform Roe corona of X. We study the question of what information on spaces X and Y one can infer when the Uniform Roe coronas of X and Y are isomorphic, and how answers to this question depend on the set theoretical axioms in play. This is joint work with Bruno Braga and Ilijas Farah.
+ Andrew Zucker Bernoulli disjointness 17/09/2018 15:10
Building on recent work of Glasner and Weiss, we will consider a countable group G and define the notion of disjointness between two G-flows X and Y. We then consider the question of when every minimal flow is disjoint from the Bernoulli shift. Time permitting, we will discuss an application of these ideas to an old problem in topological dynamics due to Ellis and/or Furstenberg.
+ Ilijas Farah Uniform Roe algebras and rigidity 03/09/2018 15:10
I will start by defining the coarse equivalence of metric spaces. This is an equivalence relation meant to capture the large scale geometry of a given space.
To a coarse metric space one can associate a C*-algebra called uniform Roe algebra.
When does isomorphism of uniform Roe algebras associated imply coarse equivalence of the underlying coarse spaces? A recent result of Spakula and Willett gives sufficient conditions in the case of coarse metric spaces. These conditions are uniform discreteness and property A (the ‘coarse’ variant of amenability). I will discuss a weakening of these conditions. Very recently, these rigidity results were extended to Roe coronas (quotients of uniform Roe algebras modulo the compact operators). No previous knowledge of coarse spaces, Roe algebras, or logic is required. (This is a joint work with Bruno De Mendoca Braga and Alessandro Vignati.)
+ Matthew Foreman Global Structure Theorems for the space of measure preserving transformations 02/07/2018 15:10
In joint work with B. Weiss we show that there is a very large class of ergodic transformations (a “cone” under the pre-ordering induced by factor maps) whose joining structure is identical to another class, the “circular systems”. The latter class is of interest because every member can be realized as a Lebesgue-measure preserving diffeomorphism of the torus T^2.

Using this theorem, we are able to conclude that the joining structure among diffeomorphisms includes that of a cone of diffeomorphisms. This solves several well-known problems such as the existence of ergodic Lebesgue measure preserving diffeomorphisms with an arbitrary compact Choquet simplices of invariant measures and the existence of measure-distal diffeomorphisms of T^2 of height greater than 2. (In fact we give examples of arbitrary countable ordinal height.)

As a bonus result we give a class of diffeomorphisms T of the torus “Godel's diffeomorphisms” for which T being isomorphic to T^-1 is independent of ZFC.
+ Delia Kesner Types Quantitatifs: Fondements et Applications 04/06/2018 15:10
Des techniques quantitatives émergent aujourd'hui dans différents domaines de l'informatique pour faire face aux défis posés par le calcul sensible à la consommation des ressources.

Dans cet exposé on discutera de la pertinence de la théorie des types quantitatifs associés aux langages de programmation d'ordre supérieur (avec filtrage, opérateurs de contrôle, réductions infinis).

En commençant par l'exemple phare du lambda-calcul, on présentera ses fondements, des extensions puissantes et plusieurs applications intéressantes.
+ Daniel Soukup High Davies-trees in infinite combinatorics 07/05/2018 15:10
The goal of this talk is to explore a general method based on trees of elementary submodels which can be used to highly simplify proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we also present the corresponding technique with countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic.
+ Noé de Rancourt Théorie de Ramsey sans principe des tiroirs, et propriété de Ramsey adverse 05/03/2018 15:10
La théorie de Ramsey de dimension infinie est une branche de la théorie de Ramsey dans laquelle on cherche à obtenir des sous-structures homogènes de structures données lorsqu'on colorie des suites infinies d'éléments de cette structure. Son théorème fondateur est le théorème de Galvin-Prikry, mais de nombreux théorèmes similaires ont été démontrés par la suite. Tous reposent sur un principe des tiroirs, c'est-à-dire un résultat dans lequel on colorie non pas des suites de points, mais seulement des points.

Le premier résultat de type Ramsey sans principe des tiroirs a été démontré par Gowers dans les années 90, dans le cadre des espaces de Banach. L'abandon du principe des tiroirs a un prix : on ne peut pas obtenir de sous-structures réellement homogènes mais seulement des sous-structures qui le sont "presque", le "presque" étant ici exprimé en terme de jeux. Dans cet exposé, je présenterai un théorème de type Ramsey sans principe des tiroir dans un cadre abstrait, généralisant à la fois le théorème de Galvin-Prikry et celui de Gowers. Ce résultat motivera l'introduction de la propriété de Ramsey stratégique, une propriété des ensembles de suites d'entiers qui, dans ZFC, est satisfaite par tous les ensembles analytiques.

J'introduira par la suite la propriété de Ramsey adverse, une propriété généralisant à la fois la propriété de Ramsey stratégique et la détermination des jeux sur les entiers. En terme d'implications, cette propriété se situe entre la détermination des jeux sur les réels et celle des jeux sur les entiers, mais on ne sait pas exactement où ; j'énoncerai quelques résultats concernant la propriété de Ramsey adverse pour les ensembles projectifs sous des hypothèses supplémentaires de théorie des ensembles, qui permettront de mieux la situer.
+ Chris Laskowski Borel complexity and potential canonical Scott sentences 26/02/2018 15:10
Given a first order theory or a sentence $\Phi$ of $L_\omega_1,\omega$, we define the class of potential canonical Scott sentences of $\Phi$. Simply by comparing cardinalities, we obtain new results about the Borel complexity of $(Mod(\Phi),\iso)$, the class of countable models of $\Phi$. In particular, we find examples of first order theories T for which Mod(T) is not Borel complete, yet the isomorphism relation on Mod(T) is not Borel.
This is joint work with Douglas Ulrich and Richard Rast.
+ Rafael Zamora Definably amenable groups and the fixed point property 19/02/2018 15:10
We proved an analogue of the fixed point property for definably amenable groups. This work is joint with J.F. Carmona, K. Davila and A. Onshuus.
+ Francisco Miraglia Abstract Algebraic Theory of Quadratic Forms and Rings (joint work with M. Dickmann) 12/02/2018 15:10
Let A be a commutative unitary semi-real (– 1 is not a sum of squares) ring in which 2 is a unit; let T = A^2 or a proper preorder of A. We shall describe first order axioms such that if the pair (A, T) is a model of these statements, then there is a special group, G_T(A), naturally associated to (A, T), faithfully coding the T-theory of diagonal quadratic forms with unit coefficients in A. Under mild restrictions, these axioms are necessary and sufficient for G_T(A) to faithfully code representation and T-isometry of non-singular diagonal quadratic forms with coefficients in A.

We shall present significant classes of rings satisfying these axioms and establish interesting results concerning the behavior of quadratic form theory over these classes of rings.

The needed concepts will be presented during the talk, which contains only part of the results published in:

M. Dickmann, F. Miraglia, Faithfully Quadratic Rings, Memoirs of the AMS, 1128, (November 2015).
+ Itaï Ben Yaacov Vers une reconstruction pour des théories non aleph0-catégoriques 20/11/2017 15:10
Soit T une théorie a0-catégorique, et G(T) le groupe d'automorphismes d'un modèle dénombrable (ou séparable, en logique continue), muni de la topologie de la convergence simple. Nous savons depuis longtemps que
1. Deux théories a0-catégoriques T, T' sont bi-interprétables ssi G(T) et G(T') sont isomorphes en tant que groupes topologiques.
2. Un groupe topologique G est (isomorphe à) un G(T), en logique classique (continue), ssi G est un groupe Polonais oligomorphe (Roelcke précompact).

Le 2 est un résultat de « reconstruction » : à partir d'un groupe topologique ayant une propriété abstraite, on produit une théorie, qui est d'ailleurs essentiellement unique. De surcroît, des propriétés modèle-théoriques de la théorie (stabilité, NIP) sont équivalentes à des propriétés dynamiques du groupe. Comme la stabilité ou NIP ont un sens pour les théories non a0-catégoriques, la question d'une généralisation de cette correspondance se pose.

Je propose une approche qui consiste à associer à une théorie non pas un groupe, mais un groupoïde topologique. En particulier, à partir de ce groupoïde on peut récupérer une théorie bi-interprétable avec la théorie du départ. Ceci est une toute première étape dans un travail en cours, la suite duquel pourrait être le problème de thèse de mon étudiant Mangraviti.
+ Zoé Chatzidakis Notions de clôtures aux différences de corps aux différences. 13/11/2017 15:10
Un corps aux différences est un corps avec un automorphisme distingué. La modèle compagne de leur théorie, ACFA, est supersimple. En analogie avec ce qui se passe pour les corps différentiels de caractéristique 0 et la théorie DCF0, on peut se demander si les modèles premiers (d'ACFA) existent et sont uniques à isomorphisme près.

Je donnerai d'abord les raisons évidentes pour une réponse négative. Puis j'investiguerai la question si sur certains corps aux différences il existe des modèles premiers uniques, et là encore, donnerai un contre-exemple.

Il se trouve cependant qu'en regardant d'autres notions de clôtures, provenant de notions de modèles aleph-epsilon saturés ou kappa-saturés, et en imposant une condition naturelle au corps de base K, on peut montrer que les modèles aleph-epsilon premiers (ou kappa-premiers) existent et sont uniques à K-isomorphisme près.

Ce résultat est faux en caractéristique positive.
+ Pablo Cubides Kovacsics Densité forte des types définissables 06/11/2017 15:10
Récemment, l'importance de la densité des types définissables a été relevée par différentes preuves de l'élimination des imaginaires dans les corps valués algébriquement clos. Dans cet exposé, on introduira des variantes de cette propriété et on donnera des exemples de théories les satisfaisant. Comme application, on obtiendra une preuve de l'élimination des imaginaires de la théorie des corps ordonnés différentielement clos (CODF). Il s'agit d'un travail un commun avec Quentin Brouette et Françoise Point.
+ Alessandro Vignati Application of logic to C*-algebras 23/10/2017 15:10
We survey through some of the most recent applications of logic to C*-algebras. In particular we introduce the basics of the model theory of C*-algebras and we survey through the different layers of saturation certain algebras can have. Finally, we exploit some of the connections between saturation and the structure of automorphisms of reduced product C*-algebras.
This will be a logician-friendly talk: no advanced knowledge of C*-algebras is needed.
+ Andrés Villaveces Around the model theory of modular invariants. 16/10/2017 15:10
The model theoretic analysis of the j-function has taken two apparently different paths in recent years. One of these has been inspired by arithmetic geometric considerations, has been done in infinitary logic and has produced some categoricity results (Harris). The other one (due initially to Freitag and Scanlon, later Aslanyan) has focused on the differential equations satisfied by the j-function. I will describe these two approaches, as well as some recent lines of generalization. The last part is joint work with Alex Cruz.
+ Ludovic Patey Introduction aux mathématiques à rebours 09/10/2017 15:10
Les mathématiques à rebours sont un domaine fondationnel qui vise à trouver les axiomes optimaux pour prouver les théorèmes de la vie de tous les jours. Elles se placent dans l'arithmétique du second ordre, avec une théorie de base, RCA, capturant informellement les "mathématiques calculables". Nous reviendrons sur les justifications historiques des mathématiques à rebours, présenterons ses principales observations, ainsi que l'approche moderne des mathématiques à rebours comme formalisme de classification de phénomènes calculatoires.
+ Jan Dobrowolski inp-minimal groups 02/10/2017 15:10
We will discuss some topics related to inp-minimal groups, including a sketch of the proof of the joint result with J. Goodrick stating that every left-ordered inp-minimal group is abelian (which generalizes P. Simon's result about bi-ordered groups).
+ Slawomir Solecki Menger compacta as projective Fraisse limits with emphasis on dimension one 29/05/2017 15:10
In each dimension d, there exists a canonical compact, second countable space, called the d-dimensional Menger space, with certain universality and homogeneity properties. For d = 0, it is the Cantor set, for d = infinity, it is the Hilbert cube. I will concentrate on the 1-dimensional Menger space. I will prove that it is a quotient of a projective Fraisse limit. I will describe how a property of projective Fraisse limits coming from Logic, called the projective extension property, can be used to prove high homogeneity of the 1-dimensional Menger space.

This is joint work with Aristotelis Panagiotopoulos.
+ Alexis Bès L'arithmétique de Skolem et ses extensions 22/05/2017 15:10
L'arithmétique de Skolem est la théorie du premier ordre des entiers naturels munis de la multiplication (sans l'addition). Cet exposé proposera un aperçu des principaux résultats de décidabilité autour de (N,*) et ses extensions, ainsi que des liens avec les automates. On présentera d'abord la preuve par Mostowski de la décidabilité de (N,*), basée sur les produits de structures et la décidabilité de l'arithmétique de Presburger, puis la preuve de Hodgson, basée sur les automates. On montrera ensuite comment la notion de produit généralisé introduite par Feferman et Vaught permet d'obtenir des extensions décidables de (N,*), comme par exemple (N,*,"x et y ont autant de diviseurs premiers") ou (N,*,"x et y sont premiers et x < y"). On verra enfin que ce dernier exemple (dû à F.Maurin), conduit à une notion naturelle d'automate pour les mots sur un alphabet infini.
+ Joanna Ochremiak Infinite constraint satisfaction problems 15/05/2017 15:10
We study the homomorphism problem for infinite relational structures which can be defined by finitely many first-order formulas over the natural numbers with equality. We determine the decidability status of this problem depending on whether the signature or/and the number of tuples in a single relation are allowed to be infinite.

Joint work with Bartek Klin, Eryk Kopczyński, Sławek Lasota and Szymon Toruńczyk.
+ Julien Melleray Mesures invariantes d'homéomorphismes minimaux 27/03/2017 15:10
Je reviendrai sur une caractérisation, due à Ibarlucia et moi-même, des ensembles de mesures invariantes d'homéomorphismes minimaux d'un espace de Cantor, et examinerai la question de savoir si cette caractérisation peut être simplifiée (en supprimant une des hypothèses dite de "divisibilité approximative"). J'expliquerai pourquoi cette caractérisation fait apparaître un lien avec de la théorie de Fraïssé et discuterai quelques questions ouvertes (selon le temps).
+ Arpita Korwar Polynomial Identity Testing of Sum of ROABPs 20/03/2017 15:10
Polynomials are fundamental objects in mathematics. Though univariate polynomials are fairly well-understood, multivariate polynomials are not. Arithmetic circuits are the primary tool used to study the complexity of polynomials in computer science. They allow for the classification of polynomials according to their complexity.

Polynomial identity testing (PIT) asks if a polynomial, input in the form of an arithmetic circuit, is identically zero.

One special kind of arithmetic circuits are read-once arithmetic branching programs (ROABPs), which can be written as a product of univariate polynomial matrices over distinct variables.

We will be studying the characterization of an ROABP. In the process, we can give a polynomial-time PIT for the sum of constantly many ROABPs.
+ Gilles Godefroy Quelques applications de l’axiome de Martin aux espaces de Banach 13/03/2017 15:10
L’axiome de Martin est un axiome qu’on peut ajouter aux axiomes de ZFC, qui est compatible avec la négation de l’hypothèse du continu et qui a pour effet de "pousser vers le dénombrable" tous les cardinaux inférieurs au continu. La théorie des espaces de Banach non séparables est assez différente suivant qu’on accepte, ou non, cet axiome. Nous verrons cela sur quelques exemples simples, qui ont en commun que l’axiome de Martin permet de construire des systèmes (presque) biorthogonaux transfinis.
+ Matthew Foreman A solution to a problem of von Neumann 06/03/2017 15:10
In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of manifolds. In modern language this is restated as classifying the equivalence relation of measure theoretic isomorphism. The main theorem in this talk is that the classification problem is impossible. The equivalence relation is not Borel. As part of the proof a “Global Structure Theorem” is proved that settle a couple of open questions about another classical problem, the “realization problem.” This is joint work with B. Weiss.
+ Isabel Müller La Conjecture de Zilber et ses contre-exemples 27/02/2017 15:10
Dans une tentative de classer la géométrie des ensembles fortement minimaux, Zilber les avait conjecturés pour se diviser en trois types différents: Les géométries triviales, les géométries qui ressemblent à des espaces vectoriels et ceux qui ressemblent à des corps. Hrushovski a ensuite réfuté cette conjecture en introduisant une construction intelligente qui avait été modifiée et utilisée beaucoup depuis. Son contre-exemple à la conjecture de Zilber a fourni une structure, qui n'était pas monobasée, donc ne pouvait pas être de type trivial ou de type espace vectoriel, mais elle interdisait une certaine configuration point-ligne-plan qui est toujours présente dans les corps. Hrushovski appela cette propriété CM-trivial et plus tard Pillay, avec quelques corrections d'Evans, à défini toute une hiérarchie de nouvelles géométries, où à la base on trouve les géométries monobasées (1-ample) et les géométries non-CM-triviales (2-ample) et sur le dessus on trouve des corps, qui sont n-ample pour tout n. Récemment, Baudisch, Pizarro et Ziegler et indépendamment Tent ont fourni des exemples prouvant que cette hiérarchie d'ampleur est stricte. Tandis que leurs exemples sont omega-stables de rang infini, il est resté ouvert si on peut trouver des géométries de rang fini qui sont au moins 2-amples mais n'interprètent pas un corps. Avec Katrin Tent, nous avons produit une structure presque fortement minimale qui est 2-ample, mais pas 3-ample, en utilisant une construction à la façon de Hrushovski. Dans cet exposé, nous donnerons un aperçu de la conjecture et de ses contre-exemples, motivant pourquoi notre nouvelle structure s'inscrit naturellement dans le tableau.
+ Charles Paperman Some news from the Crane Beach 20/02/2017 15:10
First-order logic over words is known to be equivalent to the circuits complexity class AC0 when equipped with arbitrary predicates. In this talk I will present result about the expressivity of first order logic when we restrict the class of predicates. I will focus in particular on the Crane Beach Property. Introduced more than a decade ago, this property is true of a logic if all the expressible languages admitting a neutral letter are regular. Finally I will present it's closely tied to the counting (in)ability of a logic as an application.
+ Alejandro Petrovich Non-classical Quantifiers Over Non-classical Logics 13/02/2017 15:10
In the literature there are several papers on the study of quantifiers in non-classical logics. Part of these works consists of considering the fragment corresponding to the study of monadic logic, that is, the fragment where the predicate symbols depend only on a fixed variable or a constant symbol. Although the connectives of propositional logic are non-classical, quantifiers are interpreted in the classical sense. The purpose of this paper is to introduce different notions of quantifiers in the particular case of the infinite valued logic (IVL) developed by Lukasiewicz. The algebraic models of this theory turn out to be MV algebras endowed with an additional operator, where MV-algebras are the algebraic models corresponding to the logic IVL. When quantifiers are interpreted classically, these structures are called monadic MV-algebras and are generalizations of the well known monadic Boolean algebras introduced by Halmos [Ha62].


[Ha62] P. Halmos, Algebraic Logic, Chelsea Publishing Company, 1962.

[Sch77] Schwartz, D., Theorie der polyadischen MV-algebren endlicher Ordnung, Math. Nachr., 78 (1977) 131--138.

[Sch80] Schwartz, D., Polyadic MV-algebras, Zeitschrift f\"ur Math. Logik und Grundla\-gen der Mathematik, 26 (1980) 561--564 .
+ L'exposé de Francisco Miraglia prévu le 30 janvier est annulé Abstract Algebraic Theory of Quadratic Forms and Rings 30/01/2017 15:10

Abstract (joint work with M. Dickmann):

Let A be a commutative unitary semi-real (– 1 is not a sum of squares) ring in which 2 is a unit; let T = A2 or a proper preorder of A. We shall describe first order axioms such that if the pair (A, T) is a model of these statements, then there is a special group, $G_T(A)$, naturally associated to (A, T), faithfully coding the T-theory of diagonal quadratic forms with unit coefficients in A. Under mild restrictions, these axioms are necessary and sufficient for $G_T(A)$ to faithfully code representation and T-isometry of non-singular diagonal quadratic forms with coefficients in A.

We shall present important classes of rings satisfying these axioms and extract significant results concerning the behavior of quadratic form theory over these classes of rings. The needed concepts will be presented during the talk, which contains only part of the results that appeared in:

M. Dickmann, F. Miraglia, Faithfully Quadratic Rings, Memoirs of the AMS, 1128, (November 2015).
+ Christina Brech Universal objects among Boolean algebras and Banach spaces 23/01/2017 15:10
An element B of a given class of Boolean algebras is universal if every other element of the class is isomorphic to a subalgebra of B. In the context of Banach spaces, we have similar notions considering isomorphisms or isometries of Banach spaces. We will discuss the existence of universal objects for some classes of Boolean algebras and of Banach spaces and their interaction. We are particularly interested in the classes of all objects of a fixed size - cardinality of Boolean algebras and density character of Banach spaces - and we shall compare the countable/separable and the uncountable/nonseparable settings.
+ Silvain Rideau Groupes définissables dans des corps enrichis 16/01/2017 15:10
Un résultat de Pillay affirme qu'un groupe définissable dans un corps différentiellement clos peut être plongé dans un groupe algébrique. Des théorèmes semblables ont été prouvés depuis pour de nombreuses structures de corps enrichis: corps séparablement clos, corps avec automorphisme générique, corps réels clos... De plus, la preuve de tous ces résultats utilisent des outils similaires développés pour étudier les groupes dans les théories stables puis simples.

Le but de mon exposé sera d'exposer certains de ces résultats de structure pour les groupes définissables ainsi que les outils utilisés. Enfin, si le temps le permet, j'expliquerais comment, dans le cas le moins compliqué, on peut s'affranchir, dans une certaines mesure, des hypothèses de stabilité ou de simplicité utilisées dans ces preuves pour pouvoir les appliquer dans des corps valués.
+ Jacques Van de Wiele Valuations 05/12/2016 15:10
Thème principal : (cours elementaire sur les) anneaux de (pre)valuation p-adique, theorie des modeles, arithmetique, approche finitaire

thèmes abordés : logique intuitionniste, algebre commutative, constructive modules, (co)homologies, categories abeliennes, (logique lineaire) topos de Faltings

Biblio principale :
Grothendieck [01.8GRO14a]
Integration Motivique (Loeser, Nicaise, Sebag) [18MOT1-11a] [18MOT2-11a]
Marc Hindry :Arithmetique [30HIN08a]
Ahmed Abbes, Michel Gros, Takeshi Tsuji :The p-adique Simpson Correspondence [18ABB16a]
Ihsen Yengui : Constructive Commutative Algebra [16.5YEN15a]
+ Benoit Monin A small history of K-triviality 28/11/2016 15:10
The Kolmogorov complexity of a string is, informally, the length of the smallest program that produces this string. We write C(s) = n to mean that the smallest program producing the string s is of length n.

An infinite binary sequence X is said to be C-trivial if the Kolmogorov complexity of its prefixes is minimal, that is, if there is a constant d such that for any n, we have C(X rest n) < C(n) + d (Here X rest n denotes the n first bits of X). It is clear that any computable (infinite binary) sequence is C-trivial. Chaitin proved that the converse holds: A sequence X is computable iff it is C-trivial (1).

Chaitin also successfully used Kolmogorov complexity to provide a formal definition of the intuitive idea we can have of a random sequence. To do so, he needed a variation of the standard Kolmogorov complexity, called "prefix Kolmogorov complexity" and denoted by K. Using this prefix Kolmorogov complexity K, he defined a sequence Z to be random if for any n we have K(Z rest n) > n - d for some constant d. The intuition is that the prefix Kolmogorov complexity should be maximal for prefixes of random sequences. This definition of randomness is still today the most studied, for many reasons that we shall not detail during the talk.

Chaitin conjectured (1) to also be true with prefix Kolmorogov complexity K, that is, X is computable iff X is K-trivial (that is, there is d such that for every n we have K(X rest n) < K(n) + d). Solovay later refuted the conjecture by constructing a non-computable K-trivial sequence A. The notion of K-triviality was born, and had yetto reveal many surprises through its numerous different characterizations, and its connections with algorithmic randomness.

After introducing the main concepts with more details, we will try during this talk to give some explanations and intuitions on the work that has been done by various people on K-triviality these last 15 years.

+ Dominique Lecomte Complexité borélienne des relations d'équivalence 21/11/2016 15:10
Nous étudions la complexité topologique des relations d'équivalence boréliennes, et donc la classe de ces dernières munie du quasi-ordre de réduction continue. Nous présenterons les premiers résultats de cette étude entamée il y a moins d'un an, ainsi que certains des théorèmes ayant permis de les obtenir.
+ Miki Hermann Minimal Distance of Propositional Models 14/11/2016 15:10
We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula (NextOtherSol, NOSOL$) or that does not need to satisfy it (NearestSol, NSOL). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments (MinSolDistance, MSD).

For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, poly-APX, or equivalence to well-known hard optimization problems.
+ Tomás Ibarlucía Belles paires de structures randomisées 07/11/2016 15:10
Un problème intriguant en théorie des modèles des structures métriques est celui de généraliser la notion de théorie mono-basée. Dans le cadre d'une théorie oméga-catégorique T, une proposition intéressante vient de considérer la théorie T_P de belles paires de modèles de T : quand est-ce T_P oméga-catégorique ? Cette propriété généralise celle d'être mono-basée dans le cas classique et s'applique à d'autres exemples importants. Malheureusement, on verra qu'elle n'est jamais satisfaite par des théories randomisées non-triviales. On rappellera ce qu'est la randomisation T^R de T, puis on classifiera les modèles séparables de (T^R)_P lorsque T est oméga-catégorique.
+ Christophe Chalons Autour des degrés ludiques 17/10/2016 15:10
+ Jordi Lopez-Abad La propriété de Ramsey approximative des matrices réelles et des espaces vectoriels normés 26/09/2016 15:10
Nous présentons la propriété de Ramsey approximative des espaces vectoriels normés de dimension finie. Nous discuterons aussi le degré de Ramsey métrique des matrices réelles et complexes, comme une version du Théorème de Graham-Leeb-Rothschild sur les Grassmanniennes d'un espace vectoriel sur un corps fini.
+ Philipp Schlicht A generalization of the Baire property 20/06/2016 15:10 Salle 1016 Bâtiment Sophie Germain
Many definable subsets of the Baire space of functions on the natural numbers satisfy the Baire property, for instance all analytic sets. However, it is well known that some simply definable subsets of the space of functions on a regular uncountable cardinal fail to satisfy the analogue to the Baire property. We introduce a more general property that is equal to the Baire property in the countable setting, and show that it is consistent that all definable subsets of the space of functions on an uncountable regular cardinal have this property. We consider applications such as the non-existence of definable well-orders.
+ Alexis Saurin Logiques à points fixes et théorie de la preuve (in)finitaire 30/05/2016 15:10 Salle 1016, bâtiment Sophie Germain
Dans cet exposé, on étudiera la théorie de la démonstration de logiques à points fixes, en se plaçant dans le cadre de la correspondance de Curry-Howard qui met en relation 1) formules logiques et types de données 2) preuves et programmes 3) procédure d'élimination des coupures et exécution d'un programme.
L'exposé conduira à discuter du contenu calculatoire des logiques à points fixes et permettra de présenter des systèmes de preuves finitaires et infinitaires pour ces logiques. En se concentrant sur le cadre infinitaire, on présentera les théorèmes de focalisation et d'élimination des coupures, résultats centraux en théorie de la démonstration, notamment pour la logique linéaire, que l'on introduira, resituera et dont on discutera les conséquences.
+ Ehud Hrushovski What can probability logic describe? 09/05/2016 15:10 Salle 1016 Bâtiment Sophie Germain
Probability quantifiers were studied by Keisler and Hoover in the 1980's,following earlier work of Carnap, Gaifmann, Krauss-Scott. I will survey some basic results on pure probability logic, where only stochastic quantifiers are allowed. The interpretative powers of this logic are drastically more limited than that of first-order logic. If the language consists of binary relations, one can interpret nothing more than spatial location (in a sense that will be explained; essentially on the Kim-Pillay space.) Subtleties increase with higher-order relations.
+ Esther Elbaz La théorie des modules des corps séparablement clos 04/04/2016 15:10 Salle 1016, bâtiment Sophie Germain

Dans [1], Pilar Dellunde, Françoise Delon et Françoise Point ont considéré les corps séparablement clos de caractéristique non nulle et de degré d’imperfection fixé comme des modules sur l'anneau des endomorphismes

$\mathbbF_p (B) \left \lbrace \alpha \right \lbrace$

où B est une p-base du corps et $\alpha$ est le morphisme de Froebénius. Après avoir axiomatisé cette théorie, les auteurs ont montré qu'elle est complète et admet l'élimination des quantificateurs dans le langage usuel des modules enrichis de symboles de fonctions additives analogues aux fonctions $p$-composantes du corps.
Dans cet exposé, nous présenterons ces résultats.

[1] The Theory of Modules of Separably Closed Fields 1
Pilar Dellunde; Françoise Delon; Françoise Point
The Journal of Symbolic Logic, Vol. 67, No. 3. (Sep., 2002), pp. 997-1015.
+ Guillaume Lagarde Bornes inférieures pour les circuits non-commutatifs : un autre Waterloo de la complexité algébrique ? 14/03/2016 15:10 Salle 1016, bâtiment Sophie Germain
On ne connait toujours pas de polynôme explicite nécessitant des circuits algébriques non-commutatifs (Circuits NC) de taille superpolynomiale.
Le cadre non-commutatif semble pourtant commode pour montrer de telle borne inférieure car la rigidité de la non-commutativité impose de nombreuses contraintes sur la manière de calculer efficacement. C'est dans ce contexte que Nisan, en 1991, fournit une borne exponentielle sur la taille des ABPs non-commutatifs (Algebraic Branching Programs) calculant le permanent. Nous montrons que ce résultat s'inscrit de manière naturelle comme cas particulier d'un théorème sur les circuits non-ambigus (c'est-à-dire ceux qui ne possèdent qu'un seul type de "parse tree") et proposons quelques pistes afin d'étendre ce résultat à des circuits de plus en plus proche de circuits NC généraux.
(Travaux en commun avec Guillaume Malod et Sylvain Perifel; Nutan Limaye et Srikanth Srinivasan)