Uli Wagner

About me

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.

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 R^d (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

• Graphs & Algorithms: Advanced Topics (with Johannes Lengler)

• Diskrete Mathematik (with Angelika Steger)

• Mittagsseminar (with Bernd Gärtner, Michael Hoffmann, Johannes Lengler, and Amgelika Steger)

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

• Graphs & Algorithms: Advanced Topics

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

• Reading Seminar (with Emo Welzl)

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

• Graphs & Algorithms: Advanced Topics (with Dan Hefetz)

• Diskrete Mathematik (with Emo Welzl)

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

Spring 2009

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

• Reading Seminar (with Emo Welzl)

Fall 2008

• Algebraic Methods in Combinatorics (with Dan Hefetz)

• Graphs & Algorithms: Advanced Topics (with Dan Hefetz)

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

• Reading Seminar (with Emo Welzl)

Spring 2008

• Topological Methods in Combinatorics and Geometry (with Jiří Matoušek)

• Approximate Methods in Geometry (with Bernd Gärtner and Emo Welzl)

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

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

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

• Discrete Geometry (with Jiří Matoušek)

• Approximate Methods in Geometry (with Bernd Gärtner and Emo Welzl)

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

Fall 2006

• Fourier-Analytic Methods in Discrete Mathematics (with Tibor Szabó)

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

Spring 2006

• Approximate Methods in Geometry (with Bernd Gärtner and Emo Welzl)

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