We study repeated bilateral trade where an adaptive σ-smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post either the same or different prices to buyers and sellers. We begin by showing that the minimax regret after $T$ rounds is of order $\sqrt{T}$ in the full-feedback scenario. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order $T^{3/4}$ ignoring log factors. We prove that this rate is optimal by presenting a surprising $T^{3/4}$ lower bound, which is the main technical contribution of the paper.[-]

Benoît Mandelbrot and Marcel-Paul Schützenberger first met at the Institut Poincaré in Paris in the 1950s, when both were working on topics in the then novel field of information theory. Their paths crossed again at the other end of the Atlantic on the East Coast where they were drawn into discussions on formal models of language. This was an important topic in the U.S. because these models could be useful for automatic translation, and for automatic coding of information and of programs for digital computers. In the late 1950s, a vivid debate raged whether probabilistic models or rather grammatical or rule-based models were appropriate for describing (natural) language, with notably Noam Chomsky and his students attacking the probabilistic approach. As Mandelbrot arrived in the U.S., the probabilistic model of language he had developed in his PhD became part of the discussion. Also Schützenberger got involved in the debate with his early work on coding theory. Eventually, Chomsky's arguments against probabilistic models would prevail. As a result, Mandelbrot's research went into a slightly different direction that would bring him to fractal geometry, whereas Schützenberger, via his frequent visits to the U.S., became one of the architects of the mathematics behind formal languages and coding theory.[-]

Wang's tiles were introduced in the 1960s and have been an inexhaustible source of undecidable problems ever since. They are unit square tiles with colored edges and fixed orientation, which can be placed together provided they share the same color on their common edge. Many decision problems involving Wang tiles follow the same global structure: given a finite set of Wang tiles, is there an algorithm to determine if they tile a particular shape or subset of the infinite grid? If we look for a tiling of the whole grid, this is the domino problem which is known to be undecidable for Z2 and many other groups. In this talk we focus on infinite snake tilings. Originally the infinite snake problem asks is there exists a tiling of a self-avoiding bi-infinite path on the grid Z2. In this talk I present how to expand the scope of domino snake problems to finitely generated groups to understand how the underlying structure affects computability. This is joint work with Nicolás Bitar.[-]

Matrices whose coefficients are univariate polynomials over a field are a basic mathematical object which arises at the core of fundamental algorithms in computer algebra: sparse or structured linear system solving, rational approximation or interpolation, division with remainder for bivariate polynomials, etc. After presenting this context, we will give an overview of recent progress on efficient computations with such matrices. Next, we will show how these results have been exploited to improve complexity bounds for a selection of problems which, interestingly, do not necessarily involve polynomial matrices a priori: computing the characteristic polynomial of a scalar matrix, performing modular composition of univariate polynomials, changing the monomial order for multivariate Gröbner bases.[-]

D-finite functions play a prominent role in computer algebra because they are well suited for representation in a symbolic software system, and because they include many functions of interest, such as special functions, orthogonal polynomials, generating functions from combinatorics, etc. Whenever one wishes to study the integral or the sum of a D-finite function, the method of creative telescoping may be applied. This method has been systematically introduced by Zeilberger in the 1990s, and since then has found applications in various different domains. In this lecture, we explain the underlying theory, review some of the history and talk about some recent developments in this area.[-]

Matrices whose coefficients are univariate polynomials over a field are a basic mathematical object which arises at the core of fundamental algorithms in computer algebra: sparse or structured linear system solving, rational approximation or interpolation, division with remainder for bivariate polynomials, etc. After presenting this context, we will give an overview of recent progress on efficient computations with such matrices. Next, we will show how these results have been exploited to improve complexity bounds for a selection of problems which, interestingly, do not necessarily involve polynomial matrices a priori: computing the characteristic polynomial of a scalar matrix, performing modular composition of univariate polynomials, changing the monomial order for multivariate Gröbner bases.[-]

This talk has a dual aim: to provide a mathematical overview of Stone duality theory, and to invite collaboration on its Lean formalization.
Stone duality is an algebraic way of looking at profinite topologies. A profinite set is a compact, T2, totally disconnected space, or, equivalently, a topological space which can be obtained as the projective limit of finite discrete spaces. Stone proved in the 1930s that the category of profinite sets is dually equivalent to that of Boolean algebras, and, more generally, that the category of spectral spaces is dually equivalent to that of bounded distributive lattices. I will explain how spectral spaces can be advantageously understood as profinite posets, also known as Priestley spaces. I will also point to more modern research that takes Stone duality further, and may touch upon some mathematical contexts where it pops up, notably topos theory and condensed mathematics.
Elements of Stone duality theory have been formalized in Lean over the past few years, and I will report on some of the most recent progress. I will also propose a number of concrete formalization goals at various levels of estimated difficulty, to provide the audience with some potential project ideas for this week.[-]

For every positive integer $n$, we introduce a set $\mathcal{T}_n$ made of $(n+3)^2$ Wang tiles (unit squares with labeled edges). We represent a tiling by translates of these tiles as a configuration $\mathbb{Z}^2 \rightarrow \mathcal{T}_n$. A configuration is valid if the common edge of adjacent tiles has the same label. For every $n \geqslant 1$, we consider the Wang shift $\Omega_n$ defined as the set of valid configurations over the tiles $\mathcal{T}_n$. The family $\left\{\Omega_n\right\}_{n \geqslant 1}$ broadens the relation between quadratic integers and aperiodic tilings beyond the omnipresent golden ratio as the dynamics of $\Omega_n$ involves the positive root $\beta$ of the polynomial $x^2-n x-1$. This root is sometimes called the $n$-th metallic mean, and in particular, the golden mean when $n=1$ and the silver mean when $n=2$. The family gathers the hallmarks of other small aperiodic sets of Wang tiles. When $n=1$, the set of Wang tiles $\mathcal{T}_1$ is equivalent to the Ammann aperiodic set of 16 Wang tiles. The tiles in $\mathcal{T}_n$ satisfy additive versions of equations verified by the Kari-Culik aperiodic sets of 14 and 13 Wang tiles. Also configurations in $\Omega_n$ are the codings of a $\mathbb{Z}^2$-action on a 2-dimensional torus by a polygonal partition like the Jeandel-Rao aperiodic set of 11 Wang tiles. The tiles can be defined as the different instances of a square shape computer chip whose inputs and outputs are 3-dimensional integer vectors. There is an almost one-to-one factor map $\Omega_n \rightarrow \mathbb{T}^2$ which commutes the shift action on $\Omega_n$ with horizontal and vertical translations by $\beta$ on $\mathbb{T}^2$. The factor map can be explicitely defined by the average of the top labels from the same row of tiles as in Kari and Culik examples. We also show that $\Omega_n$ is self-similar, aperiodic and minimal for the shift action. Also, there exists a polygonal partition of $\mathbb{T}^2$ which we show is a Markov partition for the toral $\mathbb{Z}^2$-action. The partition and the sets of Wang tiles are symmetric which makes them, like Penrose tilings, worthy of investigation. Details can be found in the preprints available at https://arxiv.org/abs/ 2312.03652 (part I) and https://arxiv.org/abs/2403. 03197 (part II). The talk will present an overview of the main results.[-]