Activity Report 2016

Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl

Institut für Theoretische Informatik
Departement Informatik
ETH Zürich
CH-8092 Zürich

phone	+41-44-632 73 92
fax	+41-44-632 10 63

Personnel

• Professors

  Fukuda, Komei
  Gärtner, Bernd
  Welzl, Emo

• Research Associates and Ph.D. Students

  Annamalai, Chidambaram
  Barba, Luis, Dr. (since Sep 1)
  Hoffmann, Michael, Dr.
  Milatz, Malte
  N. Zehmakan, Ahad
  Nummenpalo, Jerri
  Pilz, Alexander, Dr. (since Feb 1)
  Schnider, Patrick
  Szedlák, May
  Thomas, Antonis
  Tyagi, Hemant (until Jun 30)
  Wettstein, Manuel

• Administration

  Salow, Andrea
  

Guests

• Hidefumi Hiraishi, The University of Tokyo, Japan (Feb 24 - Mar 22), Host: K. Fukuda.
• Torsten Mütze, TU Berlin, Germany (Feb 29)
  A new combinatorial Gray code for balanced combinations (Mittagsseminar, Feb 29, 2016), Host: E. Welzl.
• Jared Tanner, University of Oxford, UK (Mar 17)
  Parallel-l0, a fully parallel algorithm for combinatorial compressed sensing (Mittagsseminar, Mar 17, 2016), Host: B. Gärtner.
• Sonoko Moriyama, Nihon University, Japan (Mar 17 - 22), Host: K. Fukuda.
• Micha Sharir, Tel Aviv University, Israel (Apr 19 - 26), Host: E. Welzl.
• Carsten Lange, TU Munich, Germany (May 20)
  Cayley gaphs of finite Coxeter groups, Colin de Verdiere matrices and convex polytopes (Mittagsseminar, May 20, 2016), Host: B. Gärtner.
• Luis Barba, Carleton University / Université Libre de Bruxelles, Canada / Belgium (Jun 6 - Jun 10)
  Incremental construction of convex polyhedra and Voronoi diagrams (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• Jean Cardinal, Université Libre de Bruxelles, Brussels, Belgium (Jun 6 - Jun 10), Host: E. Welzl.
• Radoslav Fulek, Institute of Science and Technology Austria, Klosterneuburg, Austria (Jun 6 - Jun 10)
  C-planarity via Perfect Matching (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• Ali D. Mehrabi, Eindhoven University of Technology, Netherlands (Jun 6 - Jun 10)
  Finding Pairwise Intersections Inside a Query Range (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• Hossein Nassajian Mojarrad, EPFL, Switzerland (Jun 6 - Jun 10), Host: E. Welzl.
• Torsten Mütze, TU Berlin, Germany (Jun 6 - Jun 10), Host: E. Welzl.
• Yoshio Okamoto, UEC Tokyo, Japan (Jun 6 - Jun 10)
  Efficient Stabilization of Cooperative Matching Games (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• Katharina Schaar, TU München, Germany (Jun 6 - Jun 10)
  An Introduction to Complex Oriented Matroids (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• József Solymosi, University of British Columbia, Vancouver, Canada (Jun 6 - Jun 10), Host: E. Welzl.
• Bettina Speckmann, TU Eindhoven, Netherlands (Jun 6 - Jun 10), Host: E. Welzl.
• Sebastian Stich, UC de Louvain, Belgium (Jun 6 - Jun 10)
  Adaptive Quasi-Newton Methods (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• Miloš Stojaković, University of Novi Sad, Serbia (Jun 6 - Jun 10)
  Computing Optimal Feed-links (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• Michael Strobel, TU München, Germany (Jun 6 - Jun 10)
  CindyJS - Interactive Visualization on Modern Devices (Combinatorial Algorithms Day, Jun 6, 2016), Host: E. Welzl.
• Phạm Văn Thắng , EPFL, Switzerland (Jun 6 - Jun 10), Host: E. Welzl.
• Claudiu Valculescu, EPFL, Switzerland (Jun 6 - Jun 10), Host: E. Welzl.
• Katharina Schaar, TU München, Germany (Aug 15 - Sep 25), Host: E. Welzl.
• Michael Strobel, TU München, Germany (Aug 15 - Sep 25), Host: E. Welzl.
• Efi Fogel, Tel Aviv University, Israel (Sep 5 - Sep 11)
  Exact Minkowski Sums of Polygons With Holes (Mittagsseminar, Sep 6, 2016), Host: E. Welzl.
• Monique Teillaud, INRIA Nancy - Grand Est - LORIA, France (Sep 6 - Sep 11)
  Delaunay triangulations on orientable surfaces of low genus (Mittagsseminar, Sep 8, 2016), Host: E. Welzl.
• Andreas Fabri, GeometryFactory, Sophia Antipolis, France (Sep 5 - Sep 11), Host: E. Welzl.
• Laurent Rineau, GeometryFactory, Sophia Antipolis, France (Sep 5 - Sep 11), Host: E. Welzl.
• Sébastien Loriot, GeometryFactory, Sophia Antipolis, France (Sep 5 - Sep 11), Host: E. Welzl.
• Clément Jamin, Liris - CNRS, Lyon, France (Sep 5 - Sep 11), Host: E. Welzl.
• Miloš Stojaković, University of Novi Sad, Serbia (Sep 25 - Sep 29)
  Faster bottleneck non-crossing matchings (Mittagsseminar, Sep 27, 2016), Host: E. Welzl.
• Matias Korman, Tohoku University, Japan (Oct 3 - Oct 22)
  Time-Space Trade-offs for Computing (High Order) Voronoi Diagrams (Mittagsseminar, Oct 06, 2016), Host: E. Welzl.
• Francisco Valero-Cuevas, University of Southern California, USA (Oct 7, 2016). Host: B. Gärtner.
• Joel Spencer, New York University, USA (Oct 13)
  The Long Journey of R(3,k) (Mittagsseminar Oct 13, 2016). Hosts: A. Steger, E. Welzl.
• Micha Sharir, Tel Aviv University, israel (Oct 20)
  Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, point location, and a very long title (Mittagsseminar Oct 20, 2016). Host: E. Welzl.
• Ola Svensson, EPFL, Switzerland (Nov 10)
  Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms (Mittagsseminar, Nov 10, 2016). Host: E. Welzl.
• Jan Foniok, Manchester Metropolitan University, UK (Nov 18)
  Hereditary graph classes, Bell numbers, and well quasi-ordering (Mittagsseminar, Nov 18, 2016), Host: B. Gärtner.
• Ali D. Mehrabi, Eindhoven University of Technology, Netherlands (Nov 21 - Dec 21), Host: E. Welzl.

Grants

• New data structures for dynamic objects in geometric spaces

  (ETH Zurich Postdoctoral Fellowship.) The main objective of this project is to discover new fundamental results in the area of computational geometry from a theoretical point of view. We study dynamic data structures and algorithms motivated by the problem of having constantly changing objects in geometric spaces. Preprocessing is crucial to obtain a good query performance, either by independently preprocessing each object, or by a general data structure that captures the proximity information of all the objects (such as Voronoi diagrams). In this setting, we aim to study the following general problem: Given a collection of objects in a geometric space that are changing over time, detect or predict interactions between them or minimize a function defined on them. This general problem depends on several parameters and the result of modifying them is a large collection of related problems that can be tackled with similar sets of tools. If we work with a collection of hyperplanes, we obtain problems like the celebrated dynamic convex hull or dynamic linear programming. If each object is a moving convex polyhedron, we can turn to intersection testing and collision detection. Other variants include fundamental problems such as dynamic Voronoi diagrams and dynamic structures for nearest-neighbors, half-emptiness or linear programming queries. The problems in this collection draw their motivation from geographical information systems, motion planning, robotics, computer graphics or simulation, but are on their own fundamental theoretical questions. While efficient algorithms and data structures exist for some of the problems mentioned above, the vast majority assume that objects are static. In reality however, information is constantly being modified and data structures need to be adapted to deal with this fact. Designing geometric data structures for these problems on constantly changing data is a challenging task and the ultimate goal of this project.

  Contact: L. Barba.
  Duration: Sep 2016 – August 2018.

• Programmieren von klein auf in der ETH Zürich

  (Financed by the Department of Computer Science, ETH Zürich, Haslerstiftung , Akademie der Wissenschaften der Schweiz.) Zusammen mit dem Departement für Informatik der ETH Zurich errichtet das Kinderlabor ein hochqualitatives und gleichzeitig allgemein zugänglichen Weiterbildungsangebot in Informatik. Zielgruppe sind Lehrpersonen in Kindergarten und Unterstufe der Primarschule (1. / 2. Klasse), auch ohne Informatik-Vorkenntnisse. In den Kursen lernen die Teilnehmenden die sogenannten Bee-Bots kennen. Das sind kindlich gestaltete Bodenroboter in Bienenform. Sie können mit vier Richtungstasten so programmiert werden, dass sie vorgegebene Wege laufen können. Zusammen mit den Bee-Bots werden passende Unterrichtsmaterialien vorgestellt und eingesetzt. Nach dem Kurs können Lehrpersonen eine „Bee-Bot-Kiste“ für die Dauer von 2 – 4 Wochen ausleihen. Auf Wunsch kommt ein Studierender der Informatik der ETH Zürich in die Klasse, um die Lehrperson beim Einsatz zu unterstützen und zu coachen.

  Contact: B. Gärtner.
  Duration: Jan 2015 – Dec 2016.

• Redundancy in Linear and Neuromuscular Systems

  (Financed by the Swiss National Science Foundation.) Understanding and removing redundancy in a given data to improve computational efficiency or discover its fundamental structure is a universal problem in science and engineering, as the data or the mathematical model to be analyzed in any realistic situation often contains redundant information that is implied by the rest. This research project has two intertwined goals, one of them theoretical, the other one driven by a concrete application. On the theoretical level, we want to understand the structure of redundancy and the complexity of redundancy removal in explicitly or implicitly given linear and more abstract systems. Here we strongly build on our expertise in computational geometry as well as combinatorial optimization. On the application side, we want to compute redundancy and assess the role of redundancy in neuromuscular control, a field that is trying to understand how the nervous system is selecting and implementing specific muscle commands that meet the constraints of specific tasks. This part of the project will be performed in close collaboration with Francisco Valero-Cuevas. He pioneered in modeling the interplay of various muscles in terms of zonotopes whose internal structure determines the possible tasks that the muscles under consideration can achieve together.

  Contact: B. Gärtner, K. Fukuda.
  Duration: Oct 2013 – Sep 2016.

• Order Types and Extremal Combinatorial Geometry

  (Erwin Schrödinger Fellowship, Financed by the Austrian Science Foundation (FWF).) For problems like counting geometric graphs on point sets, we are usually not interested in the exact position of the points, but how they are placed relative to each other. The “order type” of a point set tells us in which order we encounter three points of the set when walking along the boundary of the triangle defined by these points in counterclockwise direction. In previous work, we defined a relation on order types by comparing the set of crossing-free geometric graphs each order type admits. We plan to obtain relations between order types that provide more insight into the structure of maximizing and minimizing point sets. In particular, we are interested in bounding the number of triangulations. We will attempt to prove a long-standing conjecture stating that the number of triangulations is minimized by a certain order type, using the insights obtained from different relations and local transformations. Apart from bounding the number of geometric graphs, we are interested in relations between different order types in its own right.

  Contact: A. Pilz.
  Duration: Mar 2016 – Mar 2019.

Publications

• Journals (with refereeing)

  I. Bárány, J. Matoušek, A. Por. Curves in R^d intersecting every hyperplane at most d+1 times. J. European Math. Soc. 18:11 (2016), 2469–2482.

  J. Emiris, V. Fisikopoulos, B. Gärtner. Efficient edge-skeleton computation for polytopes defined by oracles. Journal of Symbolic Computation 73:C (2016), 139–152.

  B. Gärtner, C. Müller, S. Stich, Variable metric random pursuit. Mathematical Programming, 156:1 (2016), 549-579.

  J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner. Untangling two systems of noncrossing curves. Israel Journal of Mathematics 212:1 (2016) 37–79.

  H. Tyagi, S. U. Stich, B. Gärtner. On Two Continuum Armed Bandit Problems in High Dimensions. Theory of Computing Systems (TOCS), 58:1 (2016), 191–222.

• Conference Proceedings (with selection process)

  H. Ahn, L. Barba, E. Oh. The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon. Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), 56:1--56:15.

  O. Aichholzer, V. Alvarez, Th. Hackl, A. Pilz, B. Speckmann, B. Vogtenhuber. An Improved Lower Bound on the Minimum Number of Triangulations. Proc. 32nd International Symposium on Computational Geometry (SoCG) (2016), 7:1–7:16.

  O. Aichholzer, Th. Hackl, M. Korman, A. Pilz, G. Rote, A. van Renssen, M. Roeloffzen, B. Vogtenhuber. Packing Short Plane Spanning Trees in Complete Geometric Graphs. Proc. 27th International Symposium on Algorithms and Computation (ISAAC) (2016), 9:1–9:12.

  O. Aichholzer, V. Kusters, W. Mulzer, A. Pilz, M. Wettstein. An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings. Proc. 26th International Symposium on Algorithms and Computation (ISAAC) (2015), 505–516.

  S. Allen, L. Barba, J. Iacono, S. Langerman. Incremental Voronoi diagrams. Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), 15:1–15:16.

  C. Annamalai. Finding Perfect Matchings in Bipartite Hypergraphs. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016), 1814–1823.

  L. Barba, M. Milatz, J. Nummenpalo, A. Thomas. Deterministic Algorithms for Unique Sink Orientations of Grids. Proc. 22nd International Computing and Combinatorics Conference (COCOON) (2016), 357–369.

  S. Fekete, A. Haas, M. Hemmer, M. Hoffmann, I. Kostitsyna, D. Krupke, F. Maurer, J. Mitchell, A. Schmidt, C. Schmidt, J. Troegel, Computing Nonsimple Polygons of Minimum Perimeter, Proc. 15th Symposium on Experimental Algorithms (SEA) (2016), 134-149.

  B. Gärtner, A. Krause, A. Kyrillidis, H. Tyagi, Learning Sparse Additive Models with Interactions in High Dimensions, Proc. 19th International Conference on Artificial Intelligence and Statistics (AISTATS) (2016), 111-120.

  B. Gärtner, J. Lengler, M. Szedlák. Random Sampling with Removal. 32nd International Symposium on Computational Geometry (SoCG 2016), 40:1–40:16.

  B. Gärtner, A. Thomas. The Niceness of Unique Sink Orientations. Proc. 20th International Workshop on Randomization and Computation (APPROX-RANDOM) (2016), 30:1-30:14.

  M. Geyer, M. Hoffmann, M. Kaufmann, V. Kusters, C.D. Tóth, The Planar Tree Packing Theorem, Proc. 32nd International Symposium on Computational Geometry (SoCG) (2016), 41:1-41:15.

  T. Hertli, I. Hurbain, S. Millius, R. A. Moser, D. Scheder, M. Szedlák. The PPSZ Algorithm for Constraint Satisfaction Problems on More Than Two Colors. Proc. 22nd International Conference on Principles and Practice of Constraint Programming (CP 2016), 412–437.

  T. Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas, T. Uno. Approximation and Hardness of Token Swapping. Proc. 24th European Symposium on Algorithms (ESA) (2016), 66:1-66:15.

• Other

  O. Aichholzer, M. Balko, Th. Hackl, A. Pilz, P. Ramos, P. Valtr, B. Vogtenhuber. Holes in 2-convex point sets. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 263–266.

  I. Bárány, K. Buchin, M. Hoffmann, A. Liebenau. An Improved Bound for Orthogeodesic Point Set Embeddings of Trees. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 47–50.

  B. Gärtner, J. Lengler, M. Szedlak. Random Sampling with Removal. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 155–158.

  C. Huemer, C. Seara, R. I. Silveira, A. Pilz. Production matrices for geometric graphs (extended abstract). Electronic Notes in Discrete Mathematics, 54 (2016), 301–306.

  P. Schnider. Packing Plane Spanning Double Stars into Complete Geometric Graphs. Abstracts 32nd European Workshop on Computational Geometry (EuroCG) (2016), 91–94.

Lectures

C. ANNAMALAI
Finding Perfect Matchings in Bipartite Hypergraphs. 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington VA, USA (Jan 12, 2016).

L. BARBA
Incremental Voronoi diagrams. 32nd International Symposium on Computational Geometry (SoCG), Boston, USA (Jun 15, 2016).

B. GÄRTNER
Smallest Enclosing Balls In and Out of CGAL. Perspectives on Geometric Software Design – 20 Years of CGAL, Stels, Switzerland (Sep 10, 2016).

M. HOFFMANN
Orthogeodesic Point Set Embeddings of Trees. 32nd European Workshop on Computational Geometry (EuroCG), Lugano, Switzerland (Mar 30, 2016).
The Planar Tree Packing Theorem. 32nd International Symposium on Computational Geometry (SoCG), Boston, USA (Jun 14, 2016).

M. MILATZ
Deterministic Algorithms for Unique Sink Orientations of Grids. 22nd International Computing and Combinatorics Conference (COCOON), Ho Chi Minh City, Vietnam (Aug 3, 2016).

A. N. ZEHMAKAN
Cellular Automata with Majority Rule. Computer Engineering Seminars, Amirkabir University of Technology, Tehran, Iran (August 1, 2016).

A. PILZ
Deciding monotonicity of complete topological graphs. Discrete Mathematics Seminar, Technische Universität Berlin, Germany (Nov 30, 2016).

P. SCHNIDER
Packing Plane Spanning Double Stars into Complete Geometric Graphs. 32nd European Workshop on Computational Geometry (EuroCG), Lugano, Switzerland (Mar 29, 2016).

A. THOMAS
The Niceness of Unique Sink Orientations. 20th International Workshop on Randomization and Computation (APPROX-RANDOM), Paris, France (Sep 09, 2016).
The Niceness of Unique Sink Orientations. MADALGO Theory Seminar, Aarhus University, Aarhus, Denmark (Sep 20, 2016)

H. TYAGI
Learning Sparse Additive Models with Interactions in High Dimensions. 19th International Conference on Artificial Intelligence and Statistics (AISTATS), Cadiz, Spain (May 11, 2016).

E. WELZL
A Short History of SAT Algorithms. Symposium on Theoretical Computer Science on the Occasion of Uwe Schöning's 60th Birthday, Univ. Ulm, Villa Eberhardt, Ulm, Germany (Jan 22, 2016).
From Crossing-Free Graphs on Wheel Sets to Polytopes with Few Vertices. Department of Computer Science, Tokyo University, Japan (Mar 24, 2016).
From Crossing-Free Graphs on Wheel Sets to Polytopes with Few Vertices. 32nd European Workshop on Computational Geometry (EuroCG), Lugano, Switzerland (Apr 1, 2016; invited talk).
Embracing Simplices (Simplicial Depth) in a Point Set. Mittagsseminar Theoretical Computer Science, Berlin Free University, Berlin, Germany (May 4, 2016).
Three Lectures on Counting in Geometry – Combinatorics and Algorithms. Fall School on Discrete Geometry and Topology, Graz University of Technology, Austria (Oct 5–6, 2016, 7 hours).

M. WETTSTEIN
Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers. A New Era of Discrete and Computational Geometry, Ascona, Switzerland (Jun 28, 2016).
Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers. Université Paris-Est Marne-la-Vallée, Paris, France (Dec 6, 2016).
Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers. École Polytechnique, Paris, France (Dec 7, 2016).

Courses and Seminars

See also the Course Catalogue.

Fall 16

• Algorithms Lab, A. Steger, E. Welzl, P. Widmayer; (VL We17-19 CAB G61; UE Mo17-19 CAB H56, Mo17-19 CAB H57, Mo17-19 HG E26.1 [+1A]), contact email: algolab@lists.inf.ethz.ch.
• Algorithms, Probability, and Computing, M. Ghaffari, A. Steger, E. Welzl, P. Widmayer; (VL Mo13-15 CAB G51, Tu14-16 CAB G51; UE We13-15 CAB G56, We16-18 CAB G52 [+1A]), contact assistant: Malte Milatz
• Geometry: Combinatorics and Algorithms, B. Gärtner, M. Hoffmann, A. Pilz, E. Welzl; (VL Th13-15 CAB G51; UE Th15-17 ML H41.1, [+1A]), contact assistant: Patrick Schnider.
• Informatik (D-MATH, D-PHYS), B. Gärtner; (VL Tu13-15 ML D28/E12; UE Tu15-17), contact assistant: Christian Zingg.
• Randomized Algorithms and Probabilistic Methods, A. Steger, E. Welzl; (VL Tu13-14 CAB G51, Th08-10 CAB G51; UE Tu16-18 CAB G51, [+1A]), contact assistant: TBA.
• Seminar der Theoretischen Informatik (Mittagsseminar), E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov; (SE Tu12-13 CAB G51, Th12-13 CAB G51).

Spring 16

• Polyhedral Computation, K. Fukuda; (VL We8-10 HG E 33.1, UE We17-18 HG E 33.1), contact assistant: May Szedlák.
• Satisfiability of Boolean Formulas - Combinatorics and Algorithms, E. Welzl; (VL Tu10-12 CAB G59, Th9-10 CAB G59, UE Tu13-15 CAB G57, [+1A]), contact assistant: Chidambaram Annamalai.
• Seminar der Theoretischen Informatik (Mittagsseminar), B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov, E. Welzl; (SE Tu12-13 CAB G51, Th12-13 CAB G51).
• Seminar Geometry: Combinatorics and Algorithms, B. Gärtner, M. Hoffmann, A. Pilz, E. Welzl; (SE Fr13-15 CAB G15.2).
• Seminar: Wie funktioniert Forschung? Algorithmen und Kombinatorik, B. Gärtner, A. Steger, E. Welzl; (SE Tu8-10 CAB G15.2).

Organization of Workshops etc.

• A New Era of Discrete & Computational Geometry, Congressi Stefano Franscini, Monte Verità, Ascona, Swizterland, Jun 26 - Jul 1, 2016, (Pankaj Agarwal, Ken Clarkson, Herbert Edelsbrunner, János Pach, Emo Welzl, Günter M. Ziegler)
• Combinatorics and Probability, Workshop at the Mathematisches Forschungsinstitut Oberwolfach, Germany, Apr 17 - 23, 2016, (Bela Bollobás, Michael Krivelevich, Oliver Riordan, Emo Welzl)
• 14th Gremo Workshop on Open Problems 2016, St. Niklausen (OW), Switzerland, Jun 6 - 10, 2016, (Michael Hoffmann).
• Perspectives on Geometric Software Design - 20 Years of CGAL, Zürich and Stels (GR), Switzerland, Sep 10-11, 2016, (Efi Fogel, Michael Hoffmann, Monique Teillaud, Emo Welzl).
• Transversal, Helly and Tverberg Type Theorems in Geometry, Combinatorics and Topology III, CMO-BIRS Workshop, Casa Matematica Oaxaca, Oaxaca, Mexico, Oct 23 - 28, 2016, (Luis Montejano, Imre Bárány, Deborah Oliveros, János Pach, Emo Welzl)

Dissertations

• Hemant Tyagi, On low dimensional models for functions in high dimensions
  Advisor: Bernd Gärtner (referee) / Co-referees: Andreas Krause, ETH Zürich, Jared Tanner, University of Oxford / Defense: Mar 17, 2016.

Master Theses

• L. Teodoro Filippini, Covering Code Construction.
  Advisors: C. Annamalai, E. Welzl / 23. 3. 2016
• Robin Leroy, On the number of crossing-free perfect matchings with designated left and right endpoints.
  Advisors: E. Welzl, M. Wettstein / 15. 10. 2016
• Georg Nührenberg, Integrated timetabling and rolling stock scheduling for public transportation.
  Advisors: B. Gärtner, M. Laumans, R. Zenklusen / 5. 7. 2016
• Pál András Papp, SAT Sparsification — Under Investigation.
  Advisors: C. Annamalai, E. Welzl / 24. 3. 2016

Bachelor and Semester Theses / Internship Projects

• Patrick Gantner, Approximating the Traveling Salesman Problem on Graphic Metrics.
  Advisors: M. Szedlák, E. Welzl / 24. 6. 2016
• Clemens Jeger, Bereichsevakuierung.
  Advisors: B. Gärtner, E. Welzl / 10. 6. 2016
• Nicolas Kirchmayr, The Kidney Exchange Problem.
  Advisors: P. Dütting, E. Welzl / 18. 5. 2016
• Janis Nertinger, Book Embeddings of Planar Graphs.
  Advisors: M. Hoffmann, E. Welzl / 2. 9. 2016
• Laurin Köhler-Schindler, Color War: Majority Cellular Automata.
  Advisors: B. Gärtner, A. N. Zehmakan, E. Welzl / 11. 11. 2016

Miscellaneous

C. ANNAMALAI
Contact assistant Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 16).
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).

L. BARBA
Teaching assistance Diskrete Mathematik (D-INFK) (Fall 16).

K. FUKUDA
Editorial Board Member of European J. Combinatorics, Computational Geometry: Theory and Applications, Applied Mathematics Research eXpress.

B. GÄRTNER
Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Mobilitätsberater des Departements Informatik.
Program committee member of

• 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark (Aug 22 - Aug 26, 2016).

M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Program committee member of

• 32nd European Workshop on Computational Geometry (EuroCG '16), Lugano, Switzerland (Mar 30 – Apr 1, 2016).
• 25th Multimedia Exposition in Computational Geometry at SoCG'16, Boston, U.S.A. (Jun 14 – 18, 2016).

Contact assistant Algorithms Lab (Fall 16).

M. MILATZ
Webmaster www-gremo (since Jul 1).
Teaching assistance Datenstukturen und Algorithmen (D-INFK) (Spring 16).
Contact assistant Algorithms, Probability, and Computing (D-INFK) (Fall 16).

A. N. ZEHMAKAN
Teaching assistance Datenstruktruren und Algorithmen (D-INFK) (Spring 16).
Teaching assistance Algorithmen und Datenstrukturen (D-INFK) (Fall 16).
Teaching assistance Diskrete Mathematik (D-INFK) (Fall 16).

J. NUMMENPALO
Teaching assistance Anwendungsnahes Programmieren mit Matlab (Spring 16).
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).

A. PILZ
Teaching assistance Parallele Programmierung (D-INFK) (Spring 16).

P. SCHNIDER
Contact assistant Geometry: Combinatorics and Algorithms (D-INFK) (Fall 16).

M. SZEDLÁK
Coordinator Mittagsseminar.
Contact assistant Polyhedral Computation (D-MATH) (Spring 16).
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).

A. THOMAS
Topic Coordinator (since Oct 1).
Teaching assistance Datenstruktruren und Algorithmen (D-INFK) (Spring 16).
Teaching assistance Algorithms Lab (D-INFK) (Fall 16).

H. TYAGI
Webmaster www-gremo (until Jun 30).

E. WELZL
Head of department and member of the board of the Department of Computer Science, ETH Zurich (since August 1).
Member of the board (deputy head) of the Department of Computer Science, ETH Zurich (until July 31).
Delegierter für Professorenwahlen an der ETH Zürich.

Coreferee for dissertations of

• Marvin Künnemann, Tight(er) Bounds for Similarity Measures, Smoothed Approximation and Broadcasting (Faculties of Natural Sciences and Technology of Saarland University, Saarbrücken, Germany; defense: August 3, 2016; referee: Benjamin Doerr; coreferees: Kurt Mehlhorn, Emo Welzl)
• Andres J. Ruiz Vargas, Simple Toplogical Graphs: Empty Triangles and Disjoint Edges, (Department of Mathematics, EPFL, Lausanne, Switzerland; defense: January 11, 2016; referee: János Pach; committee: K. Hess Bellwald (chair), F. Eisenbrand, G. Tóth, E. Welzl)

Editorial/Advisory Board member of

• ACM Transactions on Computation Theory, (Lance Fortnow, Ed.), ACM.
• Computational Geometry - Theory and Applications, (K. Mehlhorn & J.-R. Sack, Eds.), Elsevier Science Publishers.
• Discrete and Computational Geometry, (J. Goodman & R. Pollack, Eds.), Springer Verlag.
• EATCS Monographs in Theoretical Computer Science, (M. Henzinger, J. Hromkovič, M. Nielsen, G. Rozenberg, A. Salomaa, Eds.), Springer Verlag.
• EATCS Texts in Theoretical Computer Science, (M. Henzinger, J. Hromkovič, M. Nielsen, G. Rozenberg, A. Salomaa, Eds.), Springer Verlag.
• Journal of Universal Computer Science, (H. Maurer, Ed.), Springer Verlag (electronic journal).
• Mathematik Kompakt, (M. Brokate, H.W. Engl, K.-H. Hoffmann, G. Kersting, G. Stroth, E. Welzl, Eds.), Birkhäuser Verlag.

Member (chair, contact person) of selection committees for

• Professor of Agricultural and Resource Economics, Department of Management, Technology and Economics (D-MTEC) and Department of Environmental Systems Science (D-USYS), ETH Zurich (chair).
• Professor or Assistant Professor (Tenure Track) of Climate Geology, Department of Earth Sciences (D-ERDW), ETH Zurich (chair).
• Professor or Assistant Professor (Tenure Track) of Experimental Geochemistry/Mineral Physics, Department of Earth Sciences (D-ERDW), ETH Zurich (chair).
• Assistant Professors (Tenure Track) of Computer Science (Software Engineering and Programming Languages, Theory, Cyber-physical Systems, Data Science), Department of Computer Science (D-INFK), ETH Zurich (contact person).

Member of the

• Fachgespräch zum BSc Informatik und MSc Informatik am Fachbereich Mathematik und Informatik, Berlin Free University (Jun 2, 2016).
• Research Field Commission (Field 5, Munich, Jan 28, 2016) and the Perspectives Commission (CPT Section, Munich, Jan 29, 2016) of the Max-Planck Society.
• Review Panel of the Transregional Collaborative Research Centre 109 “Discretization in Geometry and Dynamics” (DFG, Munich, Jan 14-15, 2016).
• (chair) Scientific Advisory Board of the Max Planck Institute for Informatics (MPI), Saarbrücken, Germany.
• Scientific Board of the Computer Science Department at Ecole normale supérieure (ENS), Paris, France.
• "Stiftungsrat" of the "Stiftung zur Förderung der mathematischen Wissenschaften in der Schweiz".
• Tenure Committee of the Department of Mathematics, ETH Zurich.

Program committee member of

• 32nd International Symposium on Computational Geometry (SoCG '16), Boston, USA (June 14-18, 2016).

M. WETTSTEIN
Teaching assistance coordinator.
Teaching assistance Algorithms, Probability, and Computing (D-INFK) (Fall 16).
Teaching assistance Algorithms Lab (D-INFK) (Fall 16).

Software

• Commercialization Agreement with GeometryFactory (www.geometryfactory.com) for packages of CGAL developed at ETH.
• 17 commercial license agreements for the Miniball software.