The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp (1973) shows that maximum bipartite matching can be solved in $O(m \sqrt{n})$ time on a graph with $n$ vertices and $m$ edges. For the case of very dense graphs, a fast matrix multiplication based approach gives a running time of $O(n^{2.371})$. These results represented the fastest known algorithms for the problem until 2013, when Madry introduced a new approach based on continuous techniques achieving much faster runtime in sparse graphs. This line of research has culminated in a spectacular recent breakthrough due to Chen et al. (2022) that gives an $m^{1+o(1)}$ time algorithm for maximum bipartite matching (and more generally, for min cost flows).

This raises a natural question: are continuous techniques essential to obtaining fast algorithms for the bipartite matching problem? In this talk, I will describe a new, purely combinatorial algorithm for bipartite matching, that runs in $\tilde{O}(m^{1/3}n^{5/3})$ time, and hence outperforms both Hopcroft-Karp and the fast matrix multiplication based algorithms on moderately dense graphs. I will also briefly discuss some subsequent work that further improves this runtime.

This is joint work with Julia Chuzhoy (TTIC).

Summary: The starting point of this talk is the structure of the object $!Bool$ in probabilistic coherent spaces. For the purpose of building a semantics interpretation for PCF_proba, it is enough to consider elements of $!Bool$ that are promotions of elements in Bool, but $!Bool$ contains also more exotic elements, that can nonetheless be seen as probabilistic samplers (in the sense that they can handle any number of query from a program !Bool → sigma to its argument, seen as a random oracle). In this work, we present a caracterisation of all total elements in !Bool: we show that they can all be seen as *continuous mixture* of promotions. The central element of this proof is an extension to the category of integrable cones of the categorical version[1] of the De Finetti theorem (that says that there is a one-to-one correspondance between the continuous probability distributions on [0,1], and the infinite exchangeable sequence of discrete random variables on booleans).

[1] B. Jacobs and S. Staton. De finetti’s construction as a categorical limit, CMCS 2020.

Dans cet exposé, je vais présenter des travaux concernant le calcul de témoins de naturalité des opérations dans les omega-catégories faibles. Intuitivement, les témoins de naturalité traduisent du fait que chacune des opération d'une omega-catégorie faible se doit d'être un omega-foncteur faible. Bien que l'on manque d'outils pour exprimer formellement cette intuition, on peut explorer ce que cela signifie en petite dimension, ce qui amène à une notion que l'on a appelée la fonctorialité des opération, puis dans un second temps à la notion de naturalité. Je vais esquisser une construction permettant d'obtenir un témoin de naturalité associé à chacune des opérations d'une omega-catégorie, en m'appuyant sur la combinatoire des carrés et de leur composition. J'illustrerai ensuite cette construction en introduisant les cellules d'Eckmann-Hilton, et en montrant que la construction des témoins de naturalité permet de déduire des cellules d'Eckmann-Hilton en dimension supérieures à partir de celles en petites dimension.

The OCaml pattern-matching compiler is unsound, it generates incorrect code in the obscure corner case where we match on a value with mutable fields, and those fields are mutated during pattern-matching – from when clauses, allocation callbacks, or an access race in concurrent execution.

We recall the overall compilation strategy of the OCaml compiler, and explain how to weaken its optimization information to remain correct on mutable data.

Dirichlet's uniform approximation theorem is a fundamental result in Diophantine approximation that gives an optimal rate of approximation. We study uniform Diophantine approximation properties on the Hecke group $H_4$ in terms of the Rosen continued fractions. For a given real number $\alpha$, the best approximations are convergents of the Rosen continued fraction and the dual Rosen continued fraction of $\alpha$. We give analogous theorems of Dirichlet uniform approximation and the Legendre theorem with optimal constants. This is joint work with Ayreena Bakhtawar and Seul Bee Lee.

Gabriel-Ulmer duality is a contravariant biequivalence between small finite-limit categories and locally finitely presentable categories, which in the spirit of Lawvere's functorial semantics can be viewed as a *theory-model duality*: small finite-limit categories C are viewed as theories, and the lfp category FL(C, Set) of finite-limit preserving Set-valued functors is viewed as category of models of of C. The opposite of C can be reconstructed up to equivalence from Lex(C,Set) as full subcategory of *compact* objects.

The talk presents a *refinement* of Gabriel-Ulmer duality which is motivated by dependent type theory: finite-limit categories are replaced by *clans*, ie categories with a terminal object and a pullback-stable class of maps which is closed under composition, reflecting the structure of syntactic categories of *generalized algebraic theories* (GATs). The category of models of every GAT/clan is lfp, and to be able to reconstruct the clan we equip it with a *weak factorization system*, which in the classical case of ordinary algebraic theories (groups, rings, …) consists of projective extensions on the left, and regular epimorphisms on the right.

Details can be found in the following preprint:

https://arxiv.org/abs/2308.11967

Polynomial models are ubiquitous in computer science, arising in the study of automata and formal languages, optimisation, game theory, control theory, and numerous other areas. In this thesis, we consider models described by polynomial systems of equations and difference equations, where the system evolves through a set of discrete time steps with polynomial updates at every step. We explore three aspects of “zero problems” for polynomial models: zero testing for algebraic expressions given by polynomials, determining the existence of zeros for polynomial systems and determining the existence of zeros for sequences satisfying recurrences with polynomial coefficients.

In the first part, we study identity testing for algebraic expressions involving radicals. That is, given a k-variate polynomial represented by an algebraic circuit and k real radicals, we examine the complexity of determining whether the polynomial vanishes on the radical input. We improve on the existing PSPACE bound, placing the problem in coNP assuming the Generalised Riemann Hypothesis (GRH). We further consider a restricted version of the problem, where the inputs are square roots of odd primes, showing that it can be decided in randomised polynomial time assuming GRH.

We next consider systems of polynomial equations, and study the complexity of determining whether a system of polynomials with polynomial coefficients has a solution. We present a number-theoretic approach to the problem, generalising techniques used for identity testing, showing the problem belongs to the complexity class AM assuming GRH. We discuss how the problem relates to determining the dimension of a complex variety, which is also known to belong to AM assuming GRH.

In the final part of this thesis, we turn our attention to sequences satisfying recurrences with polynomial coefficients. We study the question of whether zero is a member of a polynomially recursive sequence arising as a sum of two hypergeometric sequences. More specifically, we consider the problem for sequences where the polynomial coefficients split over the field of rationals Q. We show its relation to the values of the Gamma function evaluated at rational points, which allows to establish decidability of the problem under the assumption of the Rohrlich-Lang conjecture. We propose a different approach to the problem based on studying the prime divisors of the sequence, allowing us to establish unconditional decidability of the problem.