ETH Zurich Department of Computer Science Institute for Theoretical Computer Science Theory of Combinatorial Algorithms

Uli Wagner

Postal address:
Institut für Theoretische Informatik
ETH Zürich, CAB G33.2
Universitätsstrasse 6
CH-8092 Zürich
Switzerland
E-mail: Uli's email address
URL: http://www.inf.ethz.ch/personal/wagneru
Tel: +41-44-632 73 39
Fax: +41-44-632 10 63
Office: CAB G33.2

About me

I received my Ph.D. in Mathematics from ETH Zürich in Summer, 2003.

After that, I spent one semester at the Mathematical Sciences Research Institute in Berkeley, one semester at the Department of Applied Mathematics and the Institute of Theoretical Computer Science at Charles University, Prague, and a year and a half at the Einstein Institute of Mathematics at the Hebrew University of Jerusalem.

Currently, I am a senior researcher (Oberassistent) at the Institute of Theoretical Computer Science at ETH Zürich.

Research

My research areas are discrete and computational geometry, i.e., I study geometric problems of a combinatorial or computational nature. A good deal of my research has been motivated by the k-set or halving hyperplane problem and its connections to crossing numbers of graphs, polytope theory, and the combinatorics of linear programming. Here is a survey artice on the topic.

More recently, I have become interested in the interplay between topology, combinatorics, and computation, specifically, in embeddability problems and topological obstructions. Typical questions include: What is the computational complexity of deciding whether a given simplicial complex embeds into Euclidean space of a given dimension? And what consequences does embeddability have for the combinatorics of the complex? The simplest instance of this problem, embedding graphs in the plane, is classical and well-understood, but in higher dimensions, many fundamental questions are still unresolved.

I have also worked on questions concerning geometric transversals (weak epsilon-nets), manifold learning and reconstruction from points samples, intersection graphs. For more details, you are invited to explore my list of publications below.

My research is supported by the Swiss National Science Foundation (SNF Projects 200021-116741, 20020-125027, 200021-125309, and 200020-138230).

Publications

  • Uli Wagner and Emo Welzl
    A Continuous Analogue of the Upper Bound Theorem (ps.gz, pdf)
    Discrete & Computational Geometry 26 (2) (2001), pp. 205-219.

    An extended abstract appeared in Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), 2000, pp. 50-56.

  • Uli Wagner
    On the Number of Corner Cuts (ps.gz, pdf)
    Advances in Applied Mathematics, 29 (2002), pp. 152-161.

  • Christoph Ambühl and Uli Wagner
    The Clique Problem in Intersection Graphs of Ellipses and Triangles (ps.gz, pdf)
    Theory of Computing Systems 38 (2), 2005, 279-292.

    An extended abstract appeared in Proc. 13th Annual International Symposium on Algorithms and Computation (ISAAC), 2002, pp. 489-500.

  • Uli Wagner
    On the Rectilinear Crossing Number of Complete Graphs (ps.gz, pdf)
    Proc. 14th Annual Symposium on Discrete Algorithms (SODA), 2003, pp. 583-588.

  • Jiří Matoušek and Uli Wagner
    New Constructions of Weak Epsilon-Net (ps.gz, pdf)
    Discrete & Computational Geometry 32 (2) (2004), pp. 195-206.

    An extended abstract appeared in Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG), 2003, pp. 129-135.

  • Joachim Giesen and Uli Wagner
    Shape Dimension and Intrinsic Metric From Samples of Manifolds with High Co-Dimension (ps.gz, pdf)
    Discrete & Computational Geometry 32 (2) (2004), pp. 245-267.

    An extended abstract appeared in Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG), 2003, pp. 329-337.

  • László Lovász, Katalin Vesztergombi, Uli Wagner, and Emo Welzl
    Convex Quadrilaterals and k-Sets (ps.gz, pdf)
    Towards a Theory of Geometric Graphs (János Pach, ed.), Contemporary Mathematics 342, American Mathematical Society, Providence, 2004, pp. 139-148.

  • Jiří Matoušek, Micha Sharir, Shakhar Smorodinsky, and Uli Wagner
    k-Sets in 4 dimensions (pdf)
    Discrete & Computational Geometry 35(2) (2006), pp. 177-191.

  • Jørgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Šámal, Bjarne Toft, and Uli Wagner
    On six problems posed by Jarik Nesetril (ps.gz, pdf)
    Topics in Discrete Mathematics (Martin Klazar, Jan Kratochvil, Martin Loebl, Jiri Matousek, Robin Thomas, eds.),
    Algorithms and Combinatorics 26 (2006), pp. 613--627.

  • Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jiří Matoušek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl
    Online conflict-free coloring for intervals (pdf)
    Siam Journal of Computing 36(5) (2006), pp. 1342--1359.

    An extended abstract appeared in Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.

  • Uli Wagner.
    On a Geometric Generalization of the Upper Bound Theorem (pdf)
    Proc. 47th Annual Symposium on the Foundations of Computer Science (FOCS), 2006, pp. 635-645.

  • Uli Wagner.
    k-Sets and k-Facets (pdf)
    Discrete and Computational Geometry - 20 Years Later (Eli Goodman, János Pach, and Ricky Pollack, eds.), Contemporary Mathematics 453, American Mathematical Society, 2008, 443-514.

  • Shakhar Smorodinsky, Marek Sulovský, and Uli Wagner
    On Center Regions and Balls Containing Many Points
    Proc. 14th Annual International Conference on Computing and Combinatorics (COCOON), 2008, pp. 363-373.

  • Kevin Buchin, Andreas Razen, Takeaki Uno, and Uli Wagner.
    Transforming Spanning Trees (pdf)
    Computational Geometry: Theory and Appications 42(8) (2009), pp. 724-730.

  • Eran Nevo and Uli Wagner.
    On the Embeddability of Skeleta of Spheres (pdf)
    Israel Journal of Mathematics 174 (2009), pp. 381-402.

  • Jiří Matoušek, Martin Tancer, and Uli Wagner.
    Hardness of Embedding Simplicial Complexes in Rd (pdf)
    Journal of the European Mathematical Society 13 (2011), pp. 259-295.

    An extended abstract appeared in Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.

  • Jiří Matoušek, Martin Tancer, and Uli Wagner
    A Geometric Proof of the Colored Tverberg Theorem (pdf)
    Discrete & Computational Geometry 47(2) (2012), pp. 245-265.
    (DOI: 10.1007/s00454-011-9368-2)

  • Uli Wagner
    Minors in Random and Expanding Hypergraphs (pdf)
    Proc. 27th Annual ACM Symposium on Computational Geometry (SoCG), 2011, pp. 351-360.

  • Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner
    Computing all maps into a sphere (arXiv preprint)
    Proceedings of the 23rd Annual Symposium on Discrete Algorithms (SODA), 2012, pp. 1-10.

  • Anna Gundert and Uli Wagner
    On Laplacians of Random Complexes (pdf)
    Proc. 28th Annual ACM Symposium on Computational Geometry (SoCG), 2012, to appear.

Coauthors

Christoph Ambühl, Jørgen Bang-Jensen, Kevin Buchin, Ke Chen, Martin Čadek, Amos Fiat, Joachim Giesen, Anna Gundert, Haim Kaplan, Marek Krčál, Meital Levy, László Lovász, Jiří Matoušek, Elchanan Mossel, Eran Nevo, János Pach, Andreas Razen, Bruce Reed, Mathias Schacht, Francis Sergeraert, Micha Sharir, Shakhar Smorodinsky, Marek Sulovský, Robert Šámal, Martin Tancer, Bjarne Toft, Takeaki Uno, Katalin Vesztergombi, Lukáš Vokřínek, Emo Welzl

Teaching

Courses and seminars I have taught at ETH Zurich since Spring 2006, in reverse chronological order. The links refer to the course webpages, which contain more information

Fall 2011

Spring 2011

  • Mittagsseminar (with Bernd Gärtner, Dan Hefetz, Michael Hoffmann, Johannes Lengler, Gabriel Nivasch, Angelika Steger, and Emo Welzl)

  • Reading Seminar (with Emo Welzl)

Fall 2010

Spring 2010

  • Metric Embeddings (with Jiří Matoušek)

  • Mittagsseminar (with Bernd Gärtner, Dan Hefetz, Michael Hoffmann, Gabriel Nivasch, and Emo Welzl)

  • Reading Seminar (with Emo Welzl)

Fall 2009

Spring 2009

Fall 2008

Spring 2008

Fall 2007

  • Mittagsseminar (with Bernd Gärtner, Michael Hoffmann, Angelika Steger, Tibor Szabó, and Emo Welzl)

  • Reading Seminar (with Tibor Szabó and Emo Welzl)

Spring 2007

Fall 2006

Spring 2006