Thu, 09 Mar 2023
17:00
L3

A strong version of Cobham's theorem

Philipp Hieronymi
(Universitat Bonn)
Abstract

Let $k,l>1$ be two multiplicatively independent integers. A subset $X$ of $\mathbb{N}^n$ is $k$-recognizable if the set of $k$-ary representations of $X$ is recognized by some finite automaton. Cobham's famous theorem states that a subset of the natural numbers is both $k$-recognizable and $l$-recognizable if and only if it is Presburger-definable (or equivalently: semilinear). We show the following strengthening. Let $X$ be $k$-recognizable, let $Y$ be $l$-recognizable such that both $X$ and $Y$ are not Presburger-definable. Then the first-order logical theory of $(\mathbb{N},+,X,Y)$ is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of $(\mathbb{N},+,X)$ is decidable. Our work strengthens and depends on earlier work of Villemaire and Bès. The essence of Cobham's theorem is that recognizability depends strongly on the choice of the base $k$. Our results strengthens this: two non-Presburger definable sets that are recognizable in multiplicatively independent bases, are not only distinct, but together computationally intractable over Presburger arithmetic. This is joint work with Christian Schulz.

Mon, 29 May 2017

16:00 - 17:00
L4

Martensitic inclusions in low-hysteresis shape memory alloys

Barbara Zwicknagl
(Universitat Bonn)
Abstract

I will report some recent analytical results on microstructures in low-hysteresis shape memory alloys. The modelling assumption is that the width of the thermal hysteresis is closely related to the minimal energy that is necessary to build a martensitic nucleus in an austenitic matrix. This energy barrier is typically modeled by (singularly perturbed) nonconvex elasticity functionals. In this talk, I will discuss recent results on the resulting variational problems, including stress-free inclusions and microstructures in the case of almost compatible phases. This talk is partly based on joint works with S. Conti, J. Diermeier, M. Klar, and D. Melching.

Thu, 04 Feb 2016
12:00
L6

Regularity of level sets and flow lines

Herbert Koch
(Universitat Bonn)
Abstract
Level sets of solutions to elliptic and parabolic problems are often much more regular than the equation suggests. I will discuss partial analyticity and consequences for level sets, the regularity of solutions to elliptic PDEs in some limit cases, and the regularity of flow lines for bounded stationary solutions to the Euler equation. This is joint work with Nikolai Nadirashvili.
Thu, 20 Feb 2014

13:00 - 14:00
L6

On extremizers for Fourier restriction inequalities

Diogo Oliveira e Silva
(Universitat Bonn)
Abstract

This talk will focus on extremizers for

a family of Fourier restriction inequalities on planar curves. It turns

out that, depending on whether or not a certain geometric condition

related to the curvature is satisfied, extremizing sequences of

nonnegative functions may or may not have a subsequence which converges

to an extremizer. We hope to describe the method of proof, which is of

concentration compactness flavor, in some detail. Tools include bilinear

estimates, a variational calculation, a modification of the usual

method of stationary phase and several explicit computations.

Mon, 05 Nov 2007

13:15 - 14:15
Oxford-Man Institute

Local Spectral Gaps on the Mean Field Ising Model and Multilevel MCMC methods

Mr. Nikolaus Schweizer
(Universitat Bonn)
Abstract

I consider the Metropolis Markov Chain based on the nearest neighbor random walk on the positive half of the Mean Field Ising Model, i.e., on those vectors from $\{−1, 1\}^N$ which contain more $1$ than $−1$. Using randomly-chosen paths I prove a lower bound for the Spectral Gap of this chain which is of order $N^-2$ and which does not depend on the inverse temperature $\beta$. In conjunction with decomposition results such as those in Jerrum, Son, Tetali and Vigoda (2004) this result may be useful for bounding the spectral gaps of more complex Markov chains on the Mean Field Ising Model which may be decomposed into Metropolis chains. As an example, I apply the result to two Multilevel Markov Chain Monte Carlo algorithms, Swapping and Simulated Tempering. Improving a result by Madras and Zheng (2002), I show that the spectral gaps of both algorithms on the (full) Mean Field Ising Model are bounded from below by the reciprocal of a polynomial in the lattice size $N$ and in the inverse temperature $\beta$.

Subscribe to Universitat Bonn