Department of Computer Science

Theory of Combinatorial Algorithms
Prof. Emo Welzl
up print 
People
Activity Report
    2015
Previous Reports
Research
Mittagsseminar
Teaching
Workshops
Social Activities

Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2015

Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl

Institut für Theoretische Informatik
Departement Informatik
ETH Zürichphone +41-44-632 73 92
CH-8092 Zürichfax+41-44-632 10 63


Personnel



Guests


  • Otfried Cheong, KAIST, South Korea (Jan 1-9)
    Approximating Convex Shapes to Minimize the Symmetric Difference (Mittagsseminar, Jan 6, 2015)
  • Uli Wagner, Institute of Science and Technology Austria, Klosterneuburg, Austria (Jan 13 -18)
  • Kenneth L. Clarkson, IBM Almaden Research Center, USA (Jan 19-23)
    A Unified Approach to Robust Regression (Mittagsseminar, Jan 20, 2015)

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

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

  • 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


Publications


  • Books

  • Journals (with refereeing)

    I. Bárány, J. Matoušek, A. Por, Curves in Rd intersecting every hyperplane at most d+1 times, J. European Math. Soc. (2014), to appear.

    D. Clemens, H. Gebauer, A. Liebenau, The random graph intuition for the tournament game, Combinatorics, Probability and Computing (2015), to appear.

    B. Gärtner, Sampling with Removal in LP-type Problems, Journal of Computational Geometry (JoCG) (2014), to appear.

    X. Goaoc, J. Matoušek, P. Paták, Z. Safernová, M. Tancer, Simplifying inclusion-exclusion formulas, Combinatorics, Probability and Computing (2014), to appear.

    J. Matoušek, Computing higher homotopy groups is W[1]-hard, Fundamenta Informaticae (2014), to appear.

    J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Untangling two systems of noncrossing curves, Israel J. Math. (2014), to appear.

    A. Thomas, J. van Leeuwen, Pure Nash Equilibria in Graphical Games and Treewidth, Algorithmica (2014), to appear.

    H. Tyagi, S. Stich, B. Gärtner, On two continuum armed bandit problems in high dimensions, Theory of Computing Systems (2014), to appear.

  • 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), to appear.

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

  • Other (including submitted work)

    J. Cardinal and V. Kusters, The Complexity of Simultaneous Geometric Graph Embedding, (2014), submitted.

    J. Cardinal, M. Hoffmann, V. Kusters, On Universal Point Sets for Planar Graphs, (2014), submitted.

    J. Cibulka, J. Matoušek, P. Paták, Three-monotone interpolation, (2014), submitted.

    K. Fukuda, B. Gärtner, M. Szedlák, Combinatorial Redundancy Removal, (2014), submitted.

    B. Gärtner, C. Müller, S. Stich, Variable Metric Random Pursuit, (2012), submitted.

    V. Kusters, B. Speckmann, Characterizing Graphs With A Sliceable Rectangular Dual, (2013), submitted.

    J. Matoušek, Z. Safernová, Multilevel polynomial partitions and simplified range searching, (2014), submitted.

    A. Pilz, E. Welzl, Order on Order Types, (2014), submitted.


Lectures


Courses and Seminars


Spring 15

See also the Course Catalogue

Fall 14

See also the Course Catalogue

Organization of Workshops etc.



Dissertations



Master Theses


  • Luca Eggemann, Survey on Random SAT,
    Advisors: Timon Hertli, Emo Welzl / to be completed
  • Nathanael Gutmann, Intersection Restricted Families of Sets,
    Advisor: Emo Welzl / to be completed

Bachelor and Semester Theses / Internship Projects


  • Stephan Ammann, Draw an outerplanar graph and a matching at the same time,
    Advisors: Michael Hoffmann, Vincent Kusters / to be completed
  • Pascal Su, Hamilton cycles in Kneser graphs,
    Advisors: Torsten Mütze, Emo Welzl / to be completed
  • Julia Wysling, Screening Rules for Support Vector Machines,
    Advisors: B. Gärtner, M. Jaggi / to be completed

Miscellaneous


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.

M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.

V. KUSTERS
Coordinator Mittagsseminar.

J. MATOUŠEK
Elected member of the

Editorial Board member of

H. TYAGI
Webmaster www-gremo.

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

Editorial/Advisory Board member of

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

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


Software


08-Jan-2015 / htyagi@inf.ethz.ch