Uli Wagner

The research of the group focuses on questions in combinatorial and computational geometry and topology. On the one hand, we study basic questions in geometry and topology from a combinatorial and algorithmic viewpoint. On the other hand, we apply methods from topology to problems in combinatorics, discrete geometry, and theoretical computer science.

For the purpose of algorithms and applications, we typically consider the geometric shapes (topological spaces) we study to be represented as simplicial complexes, i.e., in terms of a combinatorial description of how to build the space from basic building blocks (simplices) of various dimensions — points (vertices), line segments (edges), triangles, tetrahedra, etc. For example, a one-dimensional simplicial complex is just a graph, given by a set of vertices and a description which pairs of vertices are joined by an edge (e.g., the layout of a computer chip or a network); higher-dimensional complexes also encode interactions between three and more vertices.

Here are some typical questions we study:

1. Given spaces X and Y, can we compute [X,Y], the set of all continuous functions from X to Y up to homotopy (continuous deformation of one function into another)?

This is a classical topic in algebraic topology. Our focus is on the question to what extent this can be done in a mechanical, automated way, i.e., by a computer program.

2. Fix a simple target space, e.g. Y=Rd. Given a space X, can we decide whether X can be embedded (without self-intersections) into Rd?

3. Assuming that a space X embeds into Rd, what can we say about its structure and its combinatorial complexity (number of simplices)?

Embeddings are also a classical topic in geometric topology. On the other hand the most basic special case of these questions, graph planarity (embedding a one-dimensional space, a graph, into the plane R2) is also a fundamental topic in graph theory and theoretical computer science that has led to a rich combinatorial and algorithmic theory with many applications. Thus, one of our goals is to study higher-dimensional generalizations of graph planarity and of closely related concepts such as graph minors, crossing numbers, expander graphs, etc. 

Contact
Uli Wagner
Institute of Science and Technology Austria (IST Austria)
Am Campus 1
A – 3400 Klosterneuburg

Phone: +43 2243 9000 5501
E-mail: uli.wagner@remove-this.ist.ac.at

CV and Publication List

Assistant
Elisabeth Hacker
Phone: +43 (0)2243 9000-1015
E-mail: elisabeth.hacker@remove-this.ist.ac.at

Team

  • Arnaud de Mesmay, Postdoc
  • Kristof Huszar, PhD Student
  • Marek Krcal, Postdoc
  • Isaac Mabillard, PhD Student
  • Martin Tancer, Postdoc

Selected Publications 

  • Matoušek M, Sedgwick, E, Tancer M, Wagner U. Embeddability in the 3-sphere is decidable. Proc. 30th Ann. ACM Symp. on Comput. Geom. (SoCG), 2014, 78–84.
  • Čadek M, Krčál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2012, 1–10.
  • Wagner U. Minors in Random and Expanding Hypergraphs. Proc. 27th Ann. ACM Symp. on Comput. Geom. (SoCG), 2011, 351–360.
  • Matoušek M, Tancer M, Wagner U. Hardness of embedding simplicial complexes in Rd, J. Eur. Math. Soc. 13(2), 2011, 259–295.

    Career

    Since 2013 Assistant Professor, IST Austria
    2012-2013 SNSF Research Assistant Professor, Institut de Mathématiques de Géométrie et Applications, EPFL Lausanne
    2008–2012 Senior Research Associate, Institute of Theoretical Computer Science, ETH Zurich
    2006–2008 Postdoctoral Researcher, Institute of Theoretical Computer Science, ETH Zürich
    2004–2006 Postdoctoral Fellow, Einstein Institute for Mathematics, The Hebrew University of Jerusalem
    2004–2004 Postdoctoral Fellow, Department for Applied Mathematics, Univerzita Karlova, Prague
    2003–2003 Postdoctoral Fellow, Mathematical Sciences Research Institute, Berkeley
    2000–2004 PhD in Mathematics, ETH Zurich
    1995–2000 Diplom in Mathematics, Freie Universität Berlin

    Selected Distinctions

    2014 Co-winner of Best Paper Award at the Symposium on Computational Geometry (SoCG)
    2012 Research Assistant Professorship Grant of Swiss National Science Foundation (SNSF)
    2012 Co-winner of Best Paper Award at Symposium of Discrete Algorithms (SODA)
    2004 Richard Rado Prize

    To top