MSO can be used not only to accept/reject words, but also to transform words into other words, e.g. the doubling function w $\mapsto$ ww. The traditional model for this is called MSO transductions; the idea is that each position of the output word is interpreted in some position of the input word, and MSO is used to define the order on output positions and their labels. I will explain that an extension, where output positions are interpreted using $k$-tuples of input positions, is (a) is also well behaved; and (b) this is surprising.

In many data-driven applications, the data follows some geometric structure, and the goal is to recover this structure. In many cases, the observed data is noisy and the recovery task is even more challenging. A common assumption is that the data lies on a low dimensional manifold. Estimating a manifold from noisy samples has proven to be a challenging task. Indeed, even after decades of research, there was no (computationally tractable) algorithm that accurately estimates a manifold from noisy samples with a constant level of noise.

In this talk, we will present a method that estimates a manifold and its tangent. Moreover, we establish convergence rates, which are essentially as good as existing convergence rates for function estimation.

This is a joint work with Barak Sober.