Activity Report 2015

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

  Gärtner, Bernd
  Fukuda, Komei
  Matoušek, Jiří (Jiří Matoušek passed away after a serious illness on March 9th, 2015; Obituary)
  Welzl, Emo

• Research Associates and Ph.D. Students

  Annamalai, Chidambaram (since Sep 15)
  Hertli, Timon (until Feb 27)
  Hoffmann, Michael, Dr.
  Kusters, Vincent
  Milatz, Malte
  Mütze, Torsten, Dr. (until Mar 31)
  Nummenpalo, Jerri
  Schnider, Patrick (since Sep 15)
  Szedlák, May
  Thomas, Antonis
  Tyagi, Hemant
  Wettstein, Manuel
  Noori Zehmakan, Abdolahad (since Sep 1)
  

• Administration

  Salow, Andrea
  

Guests

---

• Otfried Cheong, KAIST, South Korea (Jan 1-9)
  Approximating Convex Shapes to Minimize the Symmetric Difference (Mittagsseminar, Jan 6, 2015), Host: E. Welzl.
• Uli Wagner, Institute of Science and Technology Austria, Klosterneuburg, Austria (Jan 13 -18), Host: E. Welzl.
• Kenneth L. Clarkson, IBM Almaden Research Center, USA (Jan 19-23)
  A Unified Approach to Robust Regression (Mittagsseminar, Jan 20, 2015), Host: E. Welzl.
• Yasuko Matsui, Tokai University, Japan (Feb 23-25), Host: K. Fukuda.
• Hidefumi Hiraishi, University of Tokyo, Japan (Feb 27 - Mar 20), Host: K. Fukuda.
• Yasuyuki Tsukamoto, Kyoto University, Japan (Mar 2-6)
  Objects with projection images just like a cube (Mittagsseminar, Mar 3, 2015), Host: K. Fukuda.
• Sonoko Moriyama, Tohoku University, Sendai, Japan (Mar 4-13), Host: B. Gärtner.
• Hanna Sumita, University of Tokyo, Japan (Mar 16-20)
  The Linear Complementarity Problem: Sparsity and Integrality (Mittagsseminar, Mar 19, 2015), Host: B. Gärtner.
• Brian Cohn, University of Southern California, USA (May 4-8, May 16-28)
  Hit-and-Run sampling of neuromechanical polytopes (Mittagsseminar, May 19, 2015), Host: B. Gärtner.
• Luis Barba, Carleton University / Université Libre de Bruxelles, Canada / Belgium (Jun 1 - Jun 5)
  Compatible connectivity-augmentation of planar disconnected graphs (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Radoslav Fulek, Institute of Science and Technology Austria, Klosterneuburg, Austria (Jun 1 - Jun 5)
  Vertical visibility among parallel polygons in three dimensions (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Luis Barba, Carleton University / Université Libre de Bruxelles, Canada / Belgium (Jun 1 - Jun 5)
  Compatible connectivity-augmentation of planar disconnected graphs (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Kristóf Huszár, Institute of Science and Technology Austria, Klosterneuburg, Austria (Jun 1 - Jun 5), Host: E. Welzl.
• Jan Kyncl, Charles University, Prague, Czech Republic and EPF Lausanne, Switzerland (Jun 1 - Jun 5), Host: E. Welzl.
• Torsten Mütze (Jun 1 - Jun 5), Host: E. Welzl.
• Márton Naszódi, EPF Lausanne, Switzerland (Jun 1 - Jun 5)
  Covering inscribed polytopes by their smaller copies (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• János Pach, EPF Lausanne, Switzerland (Jun 1 - Jun 5), Host: E. Welzl.
• Vera Rosta, Alfred Renyi Institute of Mathematics, Budapest, Hungary (Jun 1 - Jun 5), Host: E. Welzl.
• Shakhar Smorodinsky, Ben-Gurion University, Be'er Sheva, Israel and EPF Lausanne, Switzerland (Jun 1 - Jun 5)
  Choosing representatives for moving points (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• József Solymosi, University of British Columbia, Vancouver, Canada (Jun 1 - Jun 5)
  On tangencies between algebraic curves (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Sebastian Stich, UC de Louvain, Belgium (Jun 1 - Jun 5)
  Solving generalized Laplacian linear systems (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Miloš Stojaković, University of Novi Sad, Serbia (Jun 1 - Jun 5)
  Winning fast in biased Maker-Breaker games (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Andres Ruiz Vargas, EPF Lausanne, Switzerland (Jun 1 - Jun 5)
  Constructing plane graphs in simple topological graphs (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Uli Wagner, Institute of Science and Technology Austria, Klosterneuburg, Austria (Jun 1 - Jun 5), Host: E. Welzl.
• Frank de Zeeuw, EPF Lausanne, Switzerland (Jun 1 - Jun 5)
  Cartesian products in Erdös geometry (Combinatorial Algorithms Day, Jun 1, 2015), Host: E. Welzl.
• Andres Ruiz Vargas, EPF Lausanne, Switzerland (Jul 14 - Jul 16)
  Disjoint edges and empty triangles in topological graphs (Mittagsseminar, Jul 16, 2015), Host: E. Welzl.
• Micha Sharir, Tel Aviv University, Israel (Jul 15 - Jul 24)
  A new look at rigidity (Mittagsseminar, Jul 21, 2015), Host: E. Welzl.
• Andrew Winslow, Université Libre de Bruxelles, Belgium (Aug 17-22)
  Tiling Isohedrally with a Polyomino (Mittagsseminar, Aug 18, 2015), Host: E. Welzl.
• Luis Barba, Carleton University / Université Libre de Bruxelles, Canada / Belgium (Aug 24 - Sep 15), Host: E. Welzl.
• Gerald Weber, Auckland University, New Zealand (Aug 26 - 28)
  Total order is not always best - notes on topological sorting (Mittagsseminar, Aug 27, 2015), Host: B. Gärtner.
• Helmut Alt, FU Berlin, Germany (Sep 3-7)
  An Approximation Algorithm for Packing Planar Convex Objects (Mittagsseminar, Sep 3, 2015), Host: E. Welzl.
• Alexander Pilz, Graz University of Technology, Austria (Sep 14 - Sep 19),
  Good Drawings: Enumeration and Pseudo-Linearity (Mittagsseminar, Sep 17, 2015), Host: E. Welzl.
• Yoshio Okamoto, UEC Tokyo, Japan (Sep 21 - Sep 25)
  Minimum-Cost b-Edge Dominating Sets on Trees (Mittagsseminar, Sep 22, 2015), Host: E. Welzl.
• Martin Aigner, Freie Universität Berlin, Germany (Nov 1-3)
  Around the Borsuk Conjecture in 80 Years (Computer Science Colloquium, Nov 2, 2015), Host: E. Welzl.
• Luis Barba, Carleton University / Université Libre de Bruxelles, Canada / Belgium (Nov 17)
  Dynamic Graph Coloring (Mittagsseminar, Nov 17, 2015), Host: E. Welzl.
• Michael Kaufmann, Universität Tübingen, Germany (Dec 4)
  Book Embedding Problems from a SAT-Solving Perspective (Mittagsseminar, Dec 4, 2015), Host: E. Welzl.
• Luis Barba, Carleton University / Université Libre de Bruxelles, Canada / Belgium (Dec 10-24), Host: E. Welzl.

Grants

---

• Crossing-Free Configurations in the Plane - Counting, Enumeration, and Sampling

  (Financed by the Swiss National Science Foundation - EuroGIGA/ComPoSe). The goal of this project is the understanding of crossing-free geometric graphs-these are graphs with an embedding on a given planar point set where the edges are drawn as straight line segments without crossings. Often we are restricted to certain types of graphs, most prominently triangulations, but also spanning cycles, spanning trees or (perfect) matchings (and crossing-free partitions), among others. A primary goal is to enumerate, count, or sample graphs of a certain type for a given point set-so these are algorithmic questions-, or to give estimates for the maximum and minimum number of such graphs on any set of n points-these are problems in extremal combinatorial geometry.

  Contact: E. Welzl, M. Wettstein.
  Duration: April 2012 - Mar 2015.

• 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.

Publications

---

• Books

  R. Cordovil, K. Fukuda, E. Gioan, and J. Ramirez~Alfonsin (editors). "Combinatorial geometries: matroids, oriented matroids and applications. Special issue in memory of Michel Las Vergnas”, European J. Combin., 50:1-3 (2015).

• Journals (with refereeing)

  J. Cardinal, M. Hoffmann, V. Kusters, On Universal Point Sets for Planar Graphs, Journal of Graph Algorithms and Applications (JGAA), 19:1 (2015), 529-547.

  J. Cardinal, V. Kusters, The Complexity of Simultaneous Geometric Graph Embedding, Journal of Graph Algorithms and Applications (JGAA), 19:1 (2015), 259–272.

  J. Cibulka, J. Matoušek, P. Paták, Three-monotone interpolation, Discrete & Computational Geometry (DCG) , 54:1 (2015), 3-21.

  D. Clemens, H. Gebauer, A. Liebenau, The random graph intuition for the tournament game, Combinatorics, Probability and Computing, 25:1 (2016), 76-88.

  B. Gärtner, Sampling with Removal in LP-type Problems, Journal of Computational Geometry (JoCG), 6:2 (2015), 93-112.

  X. Goaoc, J. Matoušek, P. Paták, Z. Safernová, M. Tancer, Simplifying inclusion-exclusion formulas, Combinatorics, Probability and Computing, 24:2 (2015), 438-456.

  J. Matoušek, Z. Patáková, Multilevel polynomial partitions and simplified range searching, Discrete & Computational Geometry, 54:1 (2015), 22-41.

  A. Thomas, J. van Leeuwen, Pure Nash Equilibria in Graphical Games and Treewidth, Algorithmica, 71:3 (2015), 581-604.

  H. Tyagi, S. Stich, B. Gärtner, On two continuum armed bandit problems in high dimensions, Theory of Computing Systems, 58:1 (2016), 191-222.

  A. Noori Zehmakan, Bin Packing Problem: A Linear Constant-Space 3/2 -Approximation Algorithm, International Journal on Computational Science and Applications (IJCSA), 5:6 (2015), 1-15.

• Conference Proceedings (with selection process)

  J. Cardinal, M. Hoffmann, V. Kusters, Cs. D. Tóth, M. Wettstein, Arc diagrams, flip distances, and Hamiltonian triangulations, 32nd Symposium on Theoretical Aspects of Computer Science (STACS) (2015), 197-210.

  F. Frati, M. Hoffmann, and V. Kusters, Simultaneous Embeddings with Few Bends and Crossings, Proc. 23rd International Symposium on Graph Drawing (GD) (2015), 166-179.

  K. Fukuda, B. Gärtner, M. Szedlák, Combinatorial Redundancy Detection, 31st International Symposium on Computational Geometry (SoCG) (2015), 315-328.

  B. Gärtner, A. Thomas, The Complexity of Recognizing Unique Sink Orientations, 32nd Symposium on Theoretical Aspects of Computer Science (STACS) (2015), 341-353.

  V. Kusters, B. Speckmann, Towards Characterizing Graphs with a Sliceable Rectangular Dual, Proc. 23rd International Symposium on Graph Drawing (GD) (2015), 460-471.

  T. Mütze, J. Nummenpalo, Efficient computation of middle levels Gray codes, Proceedings of the 23rd European Symposium on Algorithms (ESA) (2015), 915-927.

  A. Pilz, E. Welzl, Order on Order Types, 31st International Symposium on Computational Geometry (SoCG) (2015), 285-299.

• Other (including submitted work)

  L. Barba, M. Hoffmann, V. Kusters, Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs, Abstracts of the 31st European Workshop on Computational Geometry (EuroCG), Ljubljana, Slovenia (2015), 53-56.

  A. Noori Zehmakan, M. Eslahi, A linear approximation algorithm for the BPP with the best possible absolute approximation ratio, (2015).

Lectures

---

C. ANNAMALAI
"Finding Perfect Matchings in Bipartite Hypergraphs", Relaxation Workshop as part of Trimester Program on Combinatorial Optimization, Hausdorff Institute of Mathematics, Bonn, Germany (Nov 16-20, 2015).

K. FUKUDA
“Pivoting for fitness", Paths, Pivots, and Practice: The Power of Optimization in Honor of Tamas Terlaky's 60th Birthday, GERAD, Montreal, Canada (Jun 11-13, 2015).

B. GÄRTNER
"The Many Facets of Smallest Enclosing Balls", Cross Border Meeting on Discrete and Computational Geometry and Applications, Université Savoie Mont Blanc, Chambéry, France (Nov 9, 2015).

M. HOFFMANN
"Arc Diagrams, Flip distances, and Hamiltonian triangulations", Algebra, Number Theory, and Discrete Mathematics Seminar, CSUN, Los Angeles, USA (Mar 18, 2015).
"Arc Diagrams, Flip distances, and Hamiltonian triangulations", Graph Drawing Seminar, Università Roma Tre, Rome, Italy (May 19, 2015).

V. KUSTERS
"Arc diagrams, flip distances, and Hamiltonian triangulations", 32nd Symposium on Theoretical Aspects of Computer Science (STACS), TU Munich, Germany (Mar 5, 2015).
"Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs", European Workshop on Computational Geometry (EuroCG), University of Ljubljana, Slovenia (Mar 16, 2015).
"Simultaneous embeddings with few bends and crossings", Graph Drawing (GD), Los Angeles, United States (Sep 25, 2015).
"Towards characterizing graphs with a sliceable rectangular dual", Graph Drawing (GD), Los Angeles, United States (Sep 26, 2015).

H. TYAGI
"Tangent space estimation for smooth embeddings of Riemannian manifolds", Information and Inference Best Paper Prize Meeting, University of Oxford, UK (Aug 24, 2015).

E. WELZL
"Order on Order Types", HA65, A Symposium in Honor of Helmut Alt's 65th Birthday, Berlin Free University, Germany (Jun 20, 2015).
“Resolving Conflicting Constraints: The Satisfiability Problem”, Austrian Computer Science Day (ACSD 1015), Vienna Technical University (Oct 15, 2015; invited talk).
“Crossing-Free Perfect Matchings (et al.) on Wheel Point Sets“, Doctoral Program Discrete Mathematics, Opening of the Second Phase, Graz Technical University, Austria (Oct 27, 2015; invited talk).
"Crossing-Free Perfect Matchings, etc., on Wheel Point Sets”, BMS Friday Colloquium (Berlin Mathematical School), Urania, Berlin, Germany (Nov 17, 2015).

Courses and Seminars

---

Fall 15

See also the Course Catalogue

• 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, E. Welzl, T. Holenstein, A. Steger; (VL Mo13-15 CAB G51, Tu14-16 CAB G51; UE We13-15 CAB G56, We13-15 CHN D44, We16-18 CAB G52 [+1A]), contact assistant: May Szedlák.
• Diskrete Mathematik (D-ITET), A. Steger, E. Welzl; (VL Mo10-12 NO C60; UE Fr10-12 biweekly) contact assistant: Johannes Lengler.
• Geometry: Combinatorics and Algorithms, B. Gärtner, M. Hoffmann, E. Welzl; (VL Th13-15 CAB G51; UE Th15-17 ML H41.1, [+1A]), contact assistant: Hemant Tyagi.
• Informatik (D-MATH, D-PHYS), B. Gärtner; (VL Tu13-15 ML D28/E12; UE Tu15-17), contact assistant: Christian Zingg.
• Theoretical Computer Science (Theoretische Informatik), J. Hromkovic, E. Welzl; (VL Tu8-10 CAB G61, Fr8-10 CAB G61; UE We13-15, UE Th16-18) contact assistant: Dr. Hans-Joachim Böckenhauer.
• Student Seminar in Combinatorics: Linear Complementarity, K. Fukuda; (SE Tu10-12 HG E33.3).
• Seminar SAT, E. Welzl; (SE Fr10-12 CAB G57) contact assistant: Chidambaram Annamalai.
• 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 15

See also the Course Catalogue

• Polyhedral Computation, K. Fukuda; (VL Tu15-17 CHN D 48, UE Tu17-18 CHN D 48).
• 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: Jerri Nummenpalo.
• 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, E. Welzl; (SE Fr13-15 CAB G15.2).
• Seminar: Wie funktioniert Forschung? Algorithmen und Kombinatorik, B. Gärtner, A. Steger, E. Welzl; (SE Tu15-17 CAB G15.2).

Organization of Workshops etc.

---

• 13th Gremo Workshop on Open Problems 2015, Feldis (GR), Switzerland, Jun 1 - 5, 2015, (Michael Hoffmann).

Dissertations

---

• Vincent Kusters, Simultaneous Embeddings
  Advisor: Emo Welzl (referee) / Co-referees: Michael Hoffmann, Michael Kaufmann, University of Tübingen / Defense: Dec 4, 2015.

Master Theses

---

• Vitor Bosshard, Random and Quantum Algorithms for Unique Sink Orientations,
  Advisors: A. Baumeler, B. Gärtner, S. Wolf / 13.10.2015
• Jérôme Dohrau, Edge Flips in Combinatorial Triangulations,
  Advisors: Michael Hoffmann, Vincent Kusters / 4.11.2015
• Luca Eggemann, Survey on Random SAT,
  Advisors: Timon Hertli, Emo Welzl / 24.2.2015
• Nathanael Gutmann, Intersection Restricted Families of Sets,
  Advisors: Torsten Mütze, Emo Welzl / 9.3.2015
• Jakob Olbrich, Screening Rules for Machine Learning Applications,
  Advisors: B. Gärtner, M. Jaggi / 9.9.2015
• Patrick Schnider, Partitions and Packings of Complete Geometric Graphs with Plane Spanning Double Stars and Paths,
  Advisors: Manuel Wettstein, Emo Welzl / 25.7.2015

Bachelor and Semester Theses / Internship Projects

---

• Stephan Ammann, Draw an outerplanar graph and a matching at the same time,
  Advisors: Michael Hoffmann, Vincent Kusters / 2.4.2015
• Michael Bühler, A new Algorithm for Linear programming,
  Advisors: B. Gärtner / 31.7.2015
• Christian Schneebeli, Polyhedral Boundary Detection with Random Walk,
  Advisors: Komei Fukuda, May Szedlák / 18.11.2015
• Pascal Su, Hamilton cycles in Kneser graphs,
  Advisors: Torsten Mütze, Emo Welzl / 23.3.2015
• Julia Wysling, Screening Rules for Support Vector Machines,
  Advisors: B. Gärtner, M. Jaggi / 15.2.2015

Miscellaneous

---

C. ANNAMALAI
Teach. Assistance Seminar SAT (D-INFK) (Fall 15).

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

T. HERTLI
Teach. Assistance Coordinator (until Feb 27, 2015).

M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Teach. Assistance Algorithms Lab (D-INFK) (Fall 15).

V. KUSTERS
Coordinator Mittagsseminar.
Teach. Assistance Modelling and Simulation (D-INFK) (Spring 15).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 15).

J. MATOUŠEK
Elected member of the

• Academia Europaea (section informatics)

Editorial Board member of

• Commentationes Mathematicae Universitatis Carolinae, (I. Netuka, Ed.), Charles University, Prague.
• Contributions to Discrete Mathematics, (K. Bezdek, N. Sauer, H. Williams, Eds.), University of Calgary, Canada (electronic journal).
• Discrete and Computational Geometry, (J. Goodman & R. Pollack, Eds.), Springer Verlag.
• Order, (D. Duffus, Ed.), Springer Verlag.
• Random Structures and Algorithm, (M. Karonski, N. Alon, A. Rucinski, Eds.), Wiley Periodicals, Inc.
• Theory of Computing, (L. Babai, Ed.), University of Chicago, USA (electronic journal).

M. MILATZ
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 15).

J. NUMMENPALO
Contact Assistant Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 15).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 15)

P. SCHNIDER
Teach. Assistance Diskrete Mathematik (D-INFK) (Fall 15).

M. SZEDLÁK
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 15).

A. THOMAS
Teach. Assistance Algorithms Lab (D-INFK) (Fall 15).

H. TYAGI
Webmaster www-gremo.
Teach. Assistance Modelling and Simulation (D-INFK) (Spring 15).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 15).
Contact Assistant Geometry: Combinatorics and Algorithms (D-INFK) (Fall 15)

E. WELZL
Member of the board (deputy head) of the Department of Computer Science, ETH Zurich.

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 for 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

• Assistant Professor of Plant Cell and Developmental Biology/Plant-Microbial Interactions, Department of Biology, ETH Zurich, (chair).
• Assistant Professors (Tenure Track) of Computer Science (Software Engineering and Programming Languages, Information Systems, Theory), Department of Computer Science (D-INFK), ETH Zurich.
• Professor of Agricultural Economies and Policy, and Professor/Assistant Professor (tenure track) 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 of Applied Mathematics, Department of Mathematics, ETH Zurich, (chair).
• Professor of Mathematics, Department of Mathematics, ETH Zurich.
• Professor / Assistant Professor (Tenure Track) of Networked Systems, Department of Information Technology and Electrical Engineering, ETH Zurich.

Member of the

• (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.
• Steering committee of the International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), India.
• "Stiftungsrat" of the "Stiftung zur Förderung der mathematischen Wissenschaften in der Schweiz".

Delegierter für Professorenwahlen an der ETH Zürich.
Elected as a corresponding member to the Austrian Academy of Sciences (OeAW).

M. WETTSTEIN
Teach. Assistance Coordinator (since Feb 28, 2015).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 15).

Software

---

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