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 38271
Room ABP 3007, Nöthnitzer Straße 46, 01062 Dresden

Research

  • probabilistic model checking
  • certification
  • discrete geometry

Teaching

I am not teaching this semester.

Papers

  1. Reachability in Dynamical Systems with Rounding (with C. Baier, S. Jantsch, T. Karimov, E. Lefaucheux, J. Ouaknine, A. Pouly, D. Purser, and M. A. Whiteland)

      Accepted for publication at FSTTCS 2020 [journal]

      Abstract: We consider reachability in dynamical systems with discrete linear updates, but with fixed decimalprecision, i.e., such that values of the system are rounded at each step. Given a matrix M ∈ Qd×d, an initial vector x ∈ Qd, a granularity g ∈ Q+ and a rounding operation [-] projecting a vector of Qd onto another vector whose every entry is a multiple of g, we are interested in the behaviour of the orbit O = <[x], [M[x]], [M[M[x]]], ... >, i.e., the trajectory of a linear dynamical system in which the state is rounded after each step. For arbitrary rounding functions with bounded effect, we show that the complexity of deciding point-to-point reachability - whether a given target y ∈ Qd belongs to O - is PSPACE-complete when no eigenvalue of M has modulus one. We also establish decidability without any restrictions on eigenvalues for several natural classes of rounding functions.

  2. Minimal witnesses for probabilistic timed automata (with S. Jantsch and C. Baier)

      Proceedings of ATVA 2020, LNCS 12302, 501-517, 2020. [arxiv] [journal]

      Abstract: Witnessing subsystems have proven to be a useful concept in the analysis of probabilistic systems, for example as diagnostic informa- tion on why a given property holds or as input to refinement algorithms. This paper introduces witnessing subsystems for reachability problems in probabilistic timed automata (PTA). Using a new operation on differ- ence bounds matrices, it is shown how Farkas certificates of finite-state bisimulation quotients of a PTA can be translated into witnessing subsys- tems. We present algorithms for the computation of minimal witnessing subsystems under three notions of minimality, which capture the timed behavior from different perspectives, and discuss their complexity.

  3. SWITSS: Computing Small Witnessing Subsystems (with S. Jantsch, H. Harder and C. Baier)

      Proceedings of FMCAD 2020, 236-244. [arxiv] [arxiv]

      Abstract: Witnessing subsystems for probabilistic reachability thresholds in discrete Markovian models are an important concept both as diagnostic information on why a property holds, and as input to refinement algorithms. We present SWITSS, a tool for the computation of Small WITnessing SubSystems. SWITSS implements exact and heuristic approaches based on reducing the problem to (mixed integer) linear programming. Returned subsystems can automatically be rendered graphically and are accompanied with a certificate which proves that the subsystem is indeed a witness.

  4. Farkas certificates and minimal witnesses for probabilistic reachability constraints (with S. Jantsch and C. Baier)

      Proceedings of TACAS 2020, LNCS 12078, 324-345, 2020. [arxiv] [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.

  5. The integral polytope group

      to appear in Advances in Geometry [arxiv] [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$.

  6. The L²-torsion polytope of amenable groups

      Documenta Mathematica 23 (2018), 1969-1993 [arxiv] [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.

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

      Geometry and Topology 22 (2018), 2647-2696 [journal] [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.

  8. The Grothendieck groups of polytopes of norms (with J. C. Cha and S. Friedl)

      Münster Journal of Mathematics 10 (2017), 75-81 [journal] [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.