How do we express the efficiency of an algorithm involving random events?

To illustrate how we do this, let us do this for the input search algorithm, both for the Classical Turing machine (CTM) and the Probabilistic Turing Machine (PTM). In both cases, it makes sense to express the number of steps needed to find the input as functions $t_{\textrm{CTM}}(d)$ and $t_{\textrm{PTM}}(d)$ of the distance $d$ of…

Ilyashenko fields based on convergent transmonomials

(Joint work with Zeinab Galal and Tobias Kaiser) I describe here the generalization of this construction to arbitrary convergent transmonomials, based on the Continuation Theorem. Definition A germ $f \in \I$ is simple if $\level(f) = \eh(f)$. For example, every convergent transmonomial is simple, as is every purely infinite germ. Recall that $$\la := \bigcup_{n…

Holomorphic continuations of definable germs

(Joint work with Tobias Kaiser) I introduce real domains in $\LL$ and angular level, and I use these notions to describe holomorphic continuations on $\LL$ of one-variable functions definable in $\Ranexp$. In this post “definable” means “definable in $\Ranexp$”. DefinitionA set $U \subseteq \LL$ is a real domain if there exist $a \gt 0$ and…

Some holomorphic continuations

(Joint work with Tobias Kaiser; this is a repost) We are interested in holomorphic continuations of one-variable functions definable in $\Ranexp$. Since $\exp$ and $\log$ are two crucial functions definable in $\Ranexp$, the natural domain on which to consider holomorphic continuations of all definable functions is the Riemann surface of the logarithm $$\LL:= (0,\infty) \times…

Close