Florian Funke

Bio

I am a postdoc at the Chair of Algebraic and Logic Foundations of Computer Science of the Technical University Dresden, headed by Christel Baier. I am also a member of the Collaborative Research Center ("Sonderforschungsbereich") 248 Center for Perspicuous Computing, funded by the Deutsche Forschungsgemeinschaft DFG.

Prior to settling in theoretical computer science, I obtained my Ph.D. in pure mathematics from the University of Bonn, supervised by Wolfgang Lück. Between Ph.D. and postdoc, I worked at Fraunhofer on applied artificial intelligence.

Contact

florian.funke (add "at" tu-dresden.de)
+49 (0) 351 463 38293
Room ABP 3004, Nöthnitzer Straße 46, 01062 Dresden

Research

  • probabilistic model checking, specifically the analysis of systems exhibiting both randomization and non-determinism
  • certification of model checking results and causal explanations thereof
  • discrete geometry with applications in computer science

Teaching

I am not teaching this semester.

Papers

  1. Farkas certificates and minimal witnesses for probabilistic reachability constraints (with Simon Jantsch and Christel Baier)

      submitted [pdf] [arxiv]

      Abstract: This paper introduces Farkas certificates for lower and upper bounds on minimal and maximal reachability probabilities in Markov decision processes (MDP), which we derive using an MDP-variant of Farkas' Lemma. The set of all such certificates is shown to form a polytope whose points correspond to witnessing subsystems of the model and the property. This allows translating the problem of finding minimal witnesses to the problem of finding vertices with a maximal number of zeros. While computing such vertices is computationally hard in general, we derive new heuristics from our formulations that exhibit competitive performance compared to state-of-the-art techniques and apply to more situations. As an argument that asymptotically better algorithms cannot be hoped for, we show that the decision version of finding minimal witnesses is NP-complete even for acyclic Markov chains.

  2. The integral polytope group

      to appear in Advances in Geometry [pdf] [arxiv]

      Abstract: We show that the Grothendieck group associated to integral polytopes in $\R^n$ is free-abelian by providing an explicit basis. Moreover, we identify the involution on this polytope group given by reflection about the origin as a sum of Euler characteristic type. We also compute the kernel of the norm map sending a polytope to its induced seminorm on the dual of $\R^n$.

  3. The L²-torsion polytope of amenable groups

      Documenta Mathematica 23 (2018), 1969-1993 [PDF] [arxiv]

      Abstract: We introduce the notion of groups of polytope class and show that torsion-free amenable groups satisfying the Atiyah Conjecture possess this property. A direct consequence is the homotopy invariance of the $L^2$-torsion polytope among $G$-CW-complexes for these groups. As another application we prove that the $L^2$-torsion polytope of an amenable group vanishes provided that it contains a non-abelian elementary amenable normal subgroup.

  4. Alexander and Thurston norms, and the Bieri-Neumann-Strebel invariants for free-by-cyclic groups (with Dawid Kielak)

      Geometry and Topology 22 (2018), 2647-2696 [pdf] [arxiv]

      Abstract: We investigate Friedl--Lück's universal $L^2$-torsion for descending HNN extensions of finitely generated free groups, and so in particular for $F_n$-by-$\Z$ groups. This invariant induces a semi-norm on the first cohomology of the group which is an analogue of the Thurston norm for $3$-manifold groups. We prove that this Thurston semi-norm is an upper bound for the Alexander semi-norm defined by McMullen, as well as for the higher Alexander semi-norms defined by Harvey. The same inequalities are known to hold for $3$-manifold groups. We also prove that the Newton polytopes of the universal $L^2$-torsion of a descending HNN extension of $F_2$ locally determine the Bieri--Neumann--Strebel invariant of the group. We give an explicit means of computing the BNS invariant for such groups. As a corollary, we prove that the Bieri--Neumann-Strebel invariant of a descending HNN extension of $F_2$ has finitely many connected components. When the HNN extension is taken over $F_n$ along a polynomially growing automorphism with unipotent image in $\GL(n, \Z)$, we show that the Newton polytope of the universal $L^2$-torsion and the BNS invariant completely determine one another. We also show that in this case the Alexander norm, its higher incarnations, and the Thurston norm all coincide.

  5. The Grothendieck groups of polytopes of norms (with Jae Choon Cha and Stefan Friedl)

      Münster Journal of Mathematics 10 (2017), 75-81 [pdf] [arxiv]

      Abstract: Polytopes in $\mathbb{R}^n$ with integral vertices form a monoid under the Minkowski sum, and the Grothendieck construction gives rise to an abelian group. Symmetric polytopes generate a subgroup. Similarly, difference bodies (which we refer to as norms) also generate a subgroup. We show that for every $n$ the two subgroups agree.