Department of Computer Science
Theory of Combinatorial Algorithms
Prof. Emo Welzl
up print 
People
Activity Report
Previous Reports
    2012
    2011
    2010
    2009
    2008
    2007
    2006
    2005
    2004
    2003
    2002
    2001
    2000
    1999
    1998
    1997
    1996
Research
Mittagsseminar
Teaching
Workshops
Social Activities
Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2011

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

  • Jiří Matoušek, Department of Applied Mathematics, Charles University, Prague, Czech Republic (Feb 3 - Jul 31)
  • József Solymosi, Department of Mathematics, University of British Columbia, Vancouver, Canada (Feb 6 - 11)
    Incidences and singularities (Mittagsseminar, Feb 15, 2011)
  • Radoslav Fulek, EPFL, Lausanne (Feb 7 - 10)
  • Filip Morić, EPFL, Lausanne (Feb 7 - 10)
  • Yoshio Okamoto, Tokyo Institute of Technology, Japan (Feb 7 - 10)
  • Miloš Stojaković, Department of Mathematics and Computer Science, University of Novi Sad, Serbia (Feb 7 - 15)
    A threshold for the Maker-Breaker clique game (Mittagsseminar, Feb 15, 2011)
  • Arnau Padrol, Universitat Politècnica de Catalunya, Barcelona, Spain (Mar 1 - Jun 30)
    Constructing Gale duals of neighborly polytopes (Mittagsseminar, May 24, 2011)
  • Kenneth Clarkson, IBM Almaden Research Center, San Jose, USA (Mar 19 - 23)
    Sublinear Optimization for Machine Learning (Mittagsseminar, Mar 22, 2011)
  • Ramamohan Paturi, University of California, San Diego CA, USA (Mar 19 - 26)
    Sparsification lemma (Mittagsseminar, Mar 23, 2011)
    Complexity of Evaluating Quantified k-CNFs (Mittagsseminar, Mar 24, 2011)
  • Micha Sharir, Tel Aviv University, Israel (Apr 6 - 20)
    From joints to distinct distances and beyond: The dawn of an algebraic era in combinatorial geometry (Mittagsseminar, Apr 12, 2011)
  • Pankaj Agarwal, Duke University, Durham NC, USA (Apr 6 - 22)
    Euclidean Bipartite Matching, Old and New Results (Mittagsseminar, Apr 14, 2011)
  • Edward D. Kim, TU Delft Netherlands (April 26-27)
    Polyhedral graph abstractions and weaker versions of the Hirsch Conjecture (Mittagsseminar, April 26, 2011)
  • Carsten Lange, Fachbereich Mathematik und Inormatik, FU Berlin, Germany (May 6 - 9)
    Optimal topological simplification of discrete functions on surfaces (Mittagsseminar, May 9, 2011)
  • József Solymosi, Department of Mathematics, University of British Columbia, Vancouver, Canada (May 6 - 9)
    Incidences and singularities (Mittagsseminar, May 6, 2011)
  • Zuzana Safernova, Institute for Theoretical Computer Science, Charles University, Prague, Czech Republic (Jun 8 - 19)
    On the nonexistence of k-reptile simplices in R^3 and R^4 (Mittagsseminar, Jun 9, 2011)
  • Eric Sedgwick, DePaul University, Chicago, USA (Jun 19 - 25)
    Recognition of a knot complement (Mittagsseminar, Jun 21, 2011)
  • Martin Tancer, Charles University, Prague, Czech Republic (Jun 19-25)
    Good covers are algorithmically unrecognizable (Mittagsseminar, Jun 22, 2011)
  • Boris Aronov, Polytechnic Institute of New York University, New York, USA (Jun 21 - 25)
    Algebra can do amazing things (Mittagsseminar, Jun 23, 2011)
  • Chandrajit Bajaj, University of Texas at Austin, Austin, USA (Jun 18 - 19)
    Octrees Revisited: Efficient Energetic Calculations and Neighborhood Maintenance for Molecular Simulations (Mittagsseminar, Jul 19, 2011)
  • Shakhar Smorodinsky, Ben-Gurion University, Be'er Sheva, Israel (Aug 11)
    Hitting Sets Online and Vertex Ranking (Mittagsseminar, Aug 11, 2011)
  • Joseph O'Rourke, Smith College, Northampton, USA (Aug 30 - Sep 2)
    New Methods for Unfolding Convex Polyhedra (Mittagsseminar, Sep 1, 2011)
  • Yoshio Okamoto, Japan Advanced Institute of Science and Technology, Nomi, Ishikawa, Japan (Sep 13)
    Vertex Angle and Crossing Angle Resolution of Leveled Tree Drawings (Mittagsseminar, Sep 13, 2011)
  • Philipp Hupp, Technische Universität München, Germany (Sep 15)
    On the I/O Complexity of Stencil Computations on 2 Dimensional Grids (Mittagsseminar, Sep 15, 2011)
  • Dominik Scheder, Aarhus University, Aarhus, Danmark (Sep 20)
    Truthful Mechanisms for Facility Location (Mittagsseminar, Sep 20, 2011)
  • Thomas Dueholm Hansen, Aarhus University, Aarhus, Danmark (Sep 20 - 25)
    Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor (Mittagsseminar, Sep 22, 2011)
  • Elad Hazan, Technion - Israel Institute of Technology, Haifa, Israel (Oct 2 - 6)
    Learning in the game of investing (Mittagsseminar, Oct 6, 2011)
  • Joachim Giesen, University Jena, Jena, Germany (Oct 3 - 6)
  • Tomasz Łuczak, Adam Mickiewicz University, Poznań, Poland (Oct 20 - 22)
    On a generalization of VC-dimension (Mittagsseminar, Oct 20, 2011)
  • Tibor Szabó, Freie Universität Berlin, Berlin, Germany (Oct 20 - 22)
    Sharp threshold for bounded degree spanning trees with many leaves or a long bare path (Mittagsseminar, Oct 21, 2011)
  • Gabriel Nivasch, EPFL Lausanne, Switzerland (Dec 6)
    Upper bounds for centerflats (Mittagsseminar, Dec 6, 2011)

Grants

  • Simultaneous Embeddings

    (Financed by the Swiss National Science Foundation). We use the term simultaneous (geometric) embedding to refer to any kind of problem in which two or more graphs are to be embedded simultaneously, usually subject to certain constraints. One reason for the strong interest in simultaneous embeddings lies in a wealth of applications in areas such as bio-informatics, network analysis, and software engineering. For instance, in order to compare two phylogenetic trees one would like to have a "nice" simultaneous drawing of two trees sharing the same set of leaves, so-called tanglegrams. More generally, simultaneous embeddings come into play whenever large or dynamically changing graphs are to be visualized. Given a large graph, only part of it can be shown at a time with a sufficient level of detail. When browsing from one such part to a neighboring one, it is desirable to have a certain overlap that is common to both parts and drawn the same way for both parts. In this way, the user can maintain her mental map and more easily keep track of her current location in the graph. In the context of dynamic graphs, a simultaneous drawing for several instances of the graph at different timesteps allows to visually examine the differences in order to, for instance, draw conclusions regarding the capacity utilization of a network. Beyond these motivating applications the study of simultaneous embeddings revealed a rich collection of interesting and challenging combinatorial and algorithmic problems, many of which are still far from being solved. The goal of this project is, on one hand, to gain more insights into some of these problems and, on the other hand, to develop new models in order to address some shortcomings of the existing settings studied so far. The project will be carried out as an international collaboration within the collaborative research project "GraDr: Graph Drawings and Representations", which comprises altogether 12 partners from seven European countries.

    Contact: M. Hoffmann, V. Kusters

  • Computational Geometric Learning

    (Financed by European Commission) High dimensional geometric data are ubiquitous in science and engineering, and thus processing and analyzing them is a core task in these disciplines. The Computational Geometric Learning project (CG Learning) aims at extending the success story of geometric algorithms with guarantees, as achieved in the CGAL library and the related EU funded research projects, to spaces of high dimensions. This is not a straightforward task. For many problems, no efficient algorithms exist that compute the exact solution in high dimensions. This behavior is commonly called the curse of dimensionality. We plan to address the curse of dimensionality by focusing on inherent structure in the data like sparsity or low intrinsic dimension, and by resorting to fast approximation algorithms. The following two kinds of approximation guarantee are particularly desirable: first, the solution approximates an objective better if more time and memory resources are employed (algorithmic guarantee), and second, the approximation gets better when the data become more dense and/or more accurate (learning theoretic guarantee). To lay the foundation of a new field---computational geometric learning---we will follow an approach integrating both theoretical and practical developments, the latter in the form of the construction of a high quality software library and application software.

    Contact: B. Gärtner, C. Müller

  • Linear Time Kernel Methods and Matrix Factorizations

    (Financed by Google Research Awards) The goal of this research is to study fast approximation algorithms for kernel methods on the one hand, and for approximate matrix factorizations and semi-definite programs on the other hand. Building on the coreset paradigm, we try to contribute to the understanding of sparsity and algorithmic performance on large scale problems of this form, and will also consider several practical applications from machine learning.

    Contact: B. Gärtner, M. Jaggi

  • Combinatorial and Computational Aspects of Embeddings

    (Financed by the Swiss National Science Foundation). The goal of this project is to study combinatorial and algorithmic questions related to the embeddability of simplicial complexes into Euclidean space and obstructions thereto. For graphs, the study of such questions has a long history and is best exemplified by classical results such as Euler's polyhedral formula, Kuratowski's characterization of planar graphs in terms of forbidden minors, or the fact that planarity is testable in linear time.
    On the topological side, embeddings of polyhedra and obstructions to their existence are also a classical and well studied topic in geometric topology. However, in contrast to the closely related topic of classifying embeddings up to isotopy, in particular knot theory, which has been studied extensively also from an algorithmic viewpoint, the computational complexity of the embeddability problem had, until recently, not been addressed.
    The first part of the present project concerns the systematic study of this complexity question. Together with J. Matousek and Martin Tancer, we have shown that embeddability of a given simplicial complex is at least NP-hard to test for a wide range of the parameters (dimension k of the complex and ambient dimension d), essentially, if they fall outside the metastable range of the Haefliger-Weber Theorem. Moreover, in some cases the problem is even algorithmically undecidable. Numerous open problems remain, such as elucidating the complexity situation within the metastable range.
    The second part of the project is concerned with extremal problems for simplicial complexes and with threshold phenomena for random simplicial complexes as introduced by Linial and Meshulam, both in the context of embeddability. A fundamental extremal question is, for instance: How many triangles can a 2-dimensional simplicial complex contain (in terms of the number of vertices or the number of edges) if it admits an embedding into 4-space? The corresponding question for random complexes is: If K is a 2-dimensional complex on n vertices where every possible triangle is chosen independently with probability p, what is the threshold probability p=p(n) for K being embeddable in 4-space?

    Contact: U. Wagner

  • k-Sets and Geometric Graphs

    (Financed by the Swiss National Science Foundation). The goal of this project is to investigate two basic and interrelated problems in discrete and computational geometry.
    The first part concerns triangulations and crossing-free geometric graphs in the plane. These structures are omnipresent, for example optimal Euclidean matchings, spanning trees and tours are crossing-free, triangulations provide structure to scattered points sets, etc. Moreover, combinatorial structures relate to this notion, e.g. well-formed parenthesis expressions or binary trees.
    While the situation is well-understood for point sets in convex position (then it amounts to Catalan structures whose investgation goes back to Euler around 1750), the general setting is much less understood. This concerns extremal problems, algorithmic counting and enumeration.
    The second part of the project concerns the combinatorics partitioning point sets in the plane by a line into two parts of prescribed sizes. The question how many such partitions there can be for a point set of a given size is known as the "k-set problem". Apart from its intrinsic interest as a combinatorial question, this problem arises in the analysis of a number of geometric algorithms, and also turns out to be pivotal for numerous other geometric questions, some of which seem at first quite unrelated.
    One focus of this part will be on identities for k-sets and k-facets through continuous motion, in particular in the 3-dimensional case. Moreover, we plan to further investigate applications of k-sets to other geometric problems, e.g. circle and sphere containment problems and to rectilinear crossing numbers.

    Contact: U. Wagner

  • Support Vector Machines: Geometry, Combinatorics and Algorithms

    (Financed by the Swiss National Science Foundation). The goal of this project is to study the geometric, combinatorial, and algorithmic foundations of support vector machines (SVM). The focus is on techniques that are orthogonal to the techniques used and developed in the machine learning community. The project will be carried out as an (inter)national collaboration, with two partners from Switzerland (ETH Zürich), and one partner from Germany (Friedrich-Schiller-Universität Jena).

    Contact: B. Gärtner, M. Jaggi

  • A Fresh Look at the Complexity of Pivoting in Linear Complementarity

    (Financed by the Swiss National Science Foundation.) We propose to study both linear and convex quadratic programming in a more general setting: by examining the linear complementarity problem with sufficient matrices. Besides providing a unifying framework for the two problems, linear complementarity also has many direct applications, e.g. in control theory, finance, algorithmic game theory.
    The tools we will use in our research can generally be described as combinatorial abstract models of optimisation problems. We concentrate on two of them: oriented matroids and unique-sink orientations.
    Several algorithms have been suggested by previous research in this area. For most of them there are both positive and negative results: they are known to be polynomial on some subclasses of the problems, but super-polynomial on other, larger classes. For many classes, however, such analysis is missing (among them are the two we consider the most important, that is, LCP with P-matrices and with sufficient matrices). At present randomised algorithms appear promising, and hence we plan to concentrate on their analysis.
    We plan to attack the problem from two sides. We aim to find new classes of problems for which some algorithm runs in polynomial (or expected polynomial) time; and we will search for new examples of abstract optimisation problems for which known algorithms are slow. This will in turn reduce the gap between positive and negative results for these algorithms. We believe that this approach will eventually lead to a strongly polynomial algorithm for the linear complementarity problem with sufficient matrices.

    Contact: K. Fukuda, ETHZ and EPFL, J. Foniok, ETHZ


Publications

  • Books

  • Journals (with refereeing)

    Y. Brise, B. Gärtner, Clarkson's Algorithm for Violator Spaces, Computational Geometry - Theory and Applications 44 (2011), 70-81.

    J. Foniok, K. Fukuda, L. Klaus, Combinatorial Characterizations of K-matrices, Linear Algebra and its Applications 434 (2011), 68-80.

    H. Gebauer, Enumerating all Hamilton Cycles and Bounding the Number of Hamilton Cycles in 3-Regular Graphs, The Electronic Journal of Combinatorics 18:1 (2011), #P132.

    H. Gebauer, Finding and Enumerating Hamilton Cycles in 4-Regular Graphs, Theoretical Computer Science 412(35) (2011), 4579-4591.

    M. Hoffmann, J. Matoušek, Y. Okamoto, P. Zumstein, The t-Pebbling Number is Eventually Linear in t, Electronic Journal of Combinatorics 18:1 (2011), #P153.

    Jiří Matoušek, Martin Tancer, and Uli Wagner, Hardness of embedding simplicial complexes in Rd , Journal of the European Mathematical Society 13:2 (2011), 259–295.

    M. Sharir, A. Sheffer, E. Welzl, On Degrees in Random Triangulations of Point Sets, Journal of Combinatorial Theory, Ser. A 118(7) (2011), 1979-1999.

  • Conference Proceedings (with selection process)

    T. Christ, Beyond Triangulation: Covering Polygons with Triangles, Proc. 12th Algorithms and Data Structures Symposium (WADS) (2011), LNCS 6844, 231-242.

    T. Christ, A. Francke, H. Gebauer, J. Matoušek, T. Uno, A Doubly Exponentially Crumbled Cake, Electronic Notes in Discrete Mathematics (38), (2011), 265-271.

    H. Gebauer, T. Szabó, G. Tardos, The Local Lemma is Tight for SAT, Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2011), 664-674.

    T. Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General, Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2011), 277-284.

    T. Hertli, R. Moser, D. Scheder, Improving PPSZ for 3-SAT using Critical Variables, Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS) (2011), 237-248.

    M. Hoffmann, M. Sharir, A. Sheffer, Cs. D. Toth, E. Welzl, Counting Plane Graphs: Flippability and Its Applications, Proc. 12th Algorithms and Data Structures Symposium (WADS) (2011), LNCS 6844, 524-535.

    R. Moser, D. Scheder, A Full Derandomization of Schöning's Algorithm, Proc. 43rd annual ACM symposium on Theory of computing (STOC) (2011), 245-252.

    U. Wagner, Minors in Random and Expanding Hypergraphs, Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG) (2011), 351-360.

  • Other (including submitted work)

    T. Christ, M. Hoffmann, Wireless Localization within Orthogonal Polyhedra, Proc. 23rd Canadian Conference on Computational Geometry (CCCG) (2011), 467-472.

    T. Christ, A. Mishra, Wireless Localization with Vertex Guards, Abstracts 27th European Workshop on Computational Geometry (EuroCG), Morschach, Switzerland (2011), 87-90.

    H. Gebauer, A. Gundert, R. Moser, Y. Okamoto, Not All Saturated 3-Forests Are Tight (2011).

    H. Nakayamka, S. Moriyama, K. Fukuda, Realizations of oriented matroids by polynomial optimization (2011).

    H. Nakayamka, S. Moriyama, K. Fukuda, Three characteristic rank-4 oriented matroids (2011).

    A. Razen, E. Welzl, Counting Crossing-Free Geometric Graphs with Exponential Speed-Up, Rainbow of Computer Science - Dedicated to Hermann Maurer on the Occasion of His 70th Birthday, Lecture Notes in Computer Science 6570 (2011), 36-46.

    E. Welzl, The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland?, Algorithms Unplugged (2011), 357-360.


Lectures

Y. BRISE
"Sparse Quadratic Programming Solver", CGAL Developer Meeting, Heraklion, Greece (Apr 13, 2011).

T. CHRIST
"Wireless Localization with Vertex Guards", 27th European Workshop on Computational Geometry (EuroCG), Morschach, Switzerland (Mar 28, 2011).
"Wireless Localization within Orthogonal Polyhedra", 23rd Canadian Conference on Computational Geometry (CCCG 2011), Fields Institute, Toronto, Canada (Aug 12, 2011).
"Beyond Triangulation: Covering Polygons with Triangles", 12th Algorithms and Data Structures Symposium (WADS 2011), NYU Polytech, Brooklyn, New York, U.S.A. (Aug 15, 2011).

B. GÄRTNER
"Support Vector Machines Meet Goldfarb Cubes", IPAM Workshop Efficiency of the Simplex Method - Quo Vadis Hirsch Conjecture, Institute for Pure And Applied Mathemtics, University of California in Los Angeles, USA (Jan 19, 2011).
"Leben und Karriere - wer muss sich anpassen?" Doktorandenkolloquium der Informatik Ruhr, Haus Nordhelle, Valbert, Germany (Oct 7, 2011)

H. GEBAUER
"The Local Lemma is Tight for SAT", 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, USA (Jan 24, 2011).
"Game Theoretic Ramsey Numbers", Pure mathematics seminar, Royal Holloway University of London, UK (Mar 1, 2011).
"Game Theoretic Ramsey Numbers", Combinatorics Study Group, Queen Mary University of London, UK (Mar 4, 2011).
"A Doubly Exponentially Crumbled Cake ", European Conference on Combinatorics, Graph Theory and Applications (EuroComb11), Rényi Institute, Budapest, Hungary (Aug 31, 2011).
"The Local Lemma is Tight For SAT", Combinatorial Geometry and Optimization Seminar, EPFL, Lausanne (Nov 3, 2011).

A. GUNDERT
"High-Dimensional 'Graph Theory'", 4th European Women in Mathematics Summer School, Lorentz Center, Leiden, The Netherlands (Jun 7, 2011).
"Expansion for 2-complexes", Noon Lecture, Department of Applied Mathematics (KAM), Charles University, Prague, Czech Republic (Oct 20, 2011).

T. HERTLI
"Improving PPSZ for 3-SAT using Crtitical Variables", 28th Symposium on Theoretical Aspects of Computer Science (STACS), TU Dortmund, Germany (Mar 10, 2011).
"3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General", China Theory Week (CTW), Department of Computer Science, Aarhus University, Denmark (Oct 10, 2011).
"3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General", 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Palm Springs CA, USA (Oct 23, 2011).

M. HOFFMANN
"Counting Plane Graphs: Flippability and Its Applications", 12th Algorithms and Data Structures Symposium (WADS 2011), NYU Polytech, Brooklyn, New York, U.S.A. (Aug 15, 2011).
"Counting Plane Graphs: Pseudo-Flippability and Applications", Seminar of Algorithms Group, TU Eindhoven, The Netherlands (Oct 13, 2011).

R. MOSER
"A full derandomization of Schoening's k-SAT algorithm", Combinatorics, Mathematisches Forschungsinstitut Oberwolfach, Germany (Jan 4, 2011).
"A full derandomization of Schoening's k-SAT algorithm", Humboldt-Universität Berlin, Germany (Jan 14, 2011).
"A survey on exact algorithms for constraint satisfaction problems", Computational Complexity of Discrete Problems, Schoss Dagstuhl, Wadern, Germany (Mar 25, 2011).
"A full derandomization of Schoening's k-SAT algorithm", Computational Complexity of Discrete Problems, Schloss Dagstuhl, Wadern, Germany (Mar 25, 2011).
"A survey on exact algorithms for constraint satisfaction problems", Universität Ulm, Germany (Jun 14, 2011).
"A Full Derandomization of Schöning's Algorithm", 43rd annual ACM symposium on Theory of computing (STOC), San Jose, California, USA (Jun 6, 2011).

D. SCHEDER
"A Full Derandomization of Schoening's k-SAT Algorithm", Algorithms and Complexity Theory Seminar, Aarhus University, Denmark (Mar 2, 2011).
"A Full Derandomization of Schoening's k-SAT Algorithm", Seminar of Algorithms Group, Warsaw University, Poland (Mar 31, 2011).

S. STICH
"Random derivative-free optimization of convex functions using a line search oracle", 5th workshop on Theory of Randomized Search Heuristics (ThRaSH 2011) Copenhagen, Danmark (Jul 9, 2011).
"Gradient-free optimization with Random Pursuit", CGLearning Review Meeting/Workshop Zürich, Switzerland (Dec 15, 2011).

U. WAGNER
"On Gromov's method of selecting heavily covered points", Combinatorial Geometry Seminar, Tel-Aviv University, Israel (Jan 2, 2011).
"Complete Minors of Hypergraphs: Random and Expanding Hypergraphs", 27th Annual Symposium on Computational Geometry, Paris, France, (Jun 14, 2011).
"Isoperimetry, Crossing Numbers, and Multiplicities of (Equivariant) Maps", Workshop on Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach, Germany, (Sep 7, 2011).
"Isoperimetric Inequalities in the Simplex and Multiplicities of Maps, after Gromov", ERC Workshop High-Complexity Discrete Geometry, Freie Universität Berlin, Germany, (Oct 25, 2011).

E. WELZL
"Zählen kreuzungsfreier Konfigurationen in der Ebene", Fakultätskolloquium, Department of Mathematics, Munich Technical University, Germany (Jan 25, 2011).
"When Conflicting Constraints Can be Resolved -- the Lovász Local Lemma and Satisfiability", Vienna ETH-day at The Erwin Schrödinger International Institute for Mathematical Physics, Vienna, Austria (Mar 4, 2011).
"Kasteleyn and the Number of Crossing-Free Matchings and Cycles on a Planar Point Set", Seminar on Computational Geometry, Leibniz-Center for Informatics, Schloss Dagstuhl, Germany (Mar 17, 2011).
"Counting Simple Polygonizations of Planar Point Sets", 23rd Canadian Conference on Computational Geometry (CCCG), Toronto, Canada (Aug 12, 2011; plenary talk).
"Counting Simple Polygonizations of Planar Point Sets", Seminar, Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, China (Oct 28, 2011).
"Counting Simple Polygonizations of Planar Point Sets", Friday Algorithms Seminar, University of Sydney, Sydney, Australia (Nov 11, 2011).


Courses and Seminars

Fall 11

See also the Course Catalogue

Spring 11

See also the Course Catalogue


Organization of Workshops etc.


Dissertations

  • Dominik Scheder, Algorithms and Extremal Properties of SAT and CSP
    Advisor: Emo Welzl (referee) / Co-referee: Ramamohan Paturi, University of California, San Diego, USA / Defense: Mar 21, 2011.
  • Marek Sulovský, Geometric Hypergraphs - k-Sets and Conflict-Free Coloring
    Advisors: Uli Wagner (co-referee), Emo Welzl (referee) / Co-referee: Boris Aronov, New York University, Polytechnic Institute, USA / Defense: Jun 23, 2011.
  • Tobias Christ, Discrete Descriptions of Geometric Objects
    Advisors: Michael Hoffmann (co-referee), Emo Welzl (referee) / Co-referee: Joseph O'Rourke, Smith College, Northampton, USA / Defense: Aug 31, 2011.
  • Martin Jaggi, Sparse Convex Optimization Methods for Machine Learning
    Advisors: Bernd Gärtner (co-referee), Emo Welzl (referee) / Co-referees: Joachim Buhmann, ETH; Joachim Giesen, Friedrich-Schiller-Univ. Jena, Germany; Elad Hazan, Technion - Israel Institute of Technology, Haifa, Israel / Defense: Oct 4, 2011.
  • Heidi Gebauer, Combinatorial Games on Graphs
    Advisors: Tibor Szabó, Freie Universität Berlin, Germany (co-referee), Emo Welzl (referee) / Co-referees: Tomasz Łuczak, Adam Mickiewicz University, Poland / Defense: Oct 21, 2011.

Master and Diploma Theses

  • Andreas Bärtschi, Coloring Variations of the Art Gallery Problem,
    Advisors: Subhash Suri (UC Santa Barbara), Emo Welzl / 25.8.2011
  • Beat Saurenmann, Linear CNF-formulas,
    Advisors: Heidi Gebauer, Timon Hertli / 1.10.2011
  • Jan Christoph Schlegel, Which metrics are planar?,
    Advisor: Uli Wagner / 30.04.2011
  • Markus Sprecher, The Complexity of P-LCP,
    Advisor: Bernd Gärtner / 5.7.2011

Bachelor and Semester Theses / Internship Projects

  • Bernhard Friedrich Brodowsky, Sparse Regularity Revisited,
    Advisor: Uli Wagner / 23.12.2011
  • Elena Fattorini, The Kidney Exchange Problem: Algorithmic and Game-Theoretic Considerations,
    Advisors: Matus Mihalek, Emo Welzl / 20.4.2011
  • Frank Mousset, Rainbow Cycles and Paths,
    Advisor: Heidi Gebauer / 22.8.2011
  • Aditya Gupta, Smallest Enclosing Balls of Points: A Faster and more Flexible Implementation,
    Advisor: Bernd Gärtner / 13.7.2011
  • Jan Christoph Schlegel, The Structure of Equilibrium Graphs in Network Creation Games,
    Advisors: Matus Mihalek, Emo Welzl / 31.5.2011
  • Markus Sprecher, What happens when P is close to K?,
    Advisor: Bernd Gärtner / 11.1.2011
  • May Szedlak, Applying the PPSZ Algorithm to Uniquely Satisfiable Constraint Satisfaction Problems,
    Advisor: Robin Moser, Dominik Scheder / 27.6.2011
  • David Tschirky, Covering a Polygon with Triangles,
    Advisor: Tobias Christ / 5.4.2011
  • Michel Verlinden, Sublinear Randomized Algorithms for SVMs,
    Advisors: Martin Jaggi, Bernd Gärtner / 22.7.2011
  • Manuel Wettstein, Clarkson Dimension,
    Advisor: Yves Brise, Bernd Gärtner / 7.7.2011

Miscellaneous

Y. BRISE
Webmaster www-gremo (until Oct 25).
Teach. Assistance Informatik I (D-MAVT) (Spring 11).
Contact Assistant Informatik (D-MATH, D-PHYS) (Fall 11).

T. CHRIST
Teach. Assistance Computational Geometry (Fall 11).

A. FRANCKE
Fulbright Foreign Student Grant 2011/12.
Visiting Student Researcher at the University of Washington, Seattle WA, USA (Sept 2011 - Aug 2012).

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

B. GÄRTNER
Member of the CGAL Editorial Board.

Program committee member of

Organisation des Kinderprogramms am Treffpunkt Science City (Nov 6, 2011).
Mitglied im Ausbildungs- und Beratungszentrum für Informatikunterricht ABZ und im Kinderlabor.
Kursleiter "Programmieren fuer Kinder" an der Primarschule Kloten.
Referent am 2. Schweizer Tag für den Informatikunterricht, Jan 14 2011.

H. GEBAUER
Teach. Assistance Coordinator (until Nov 20).
Contact Assistant Graphs and Algorithms: Advanced Topics (D-INFK) (Fall 11).

A. GUNDERT
Teach. Assistanc Topological Methods in Combinatorics and Geometry (Spring 11).

T. HERTLI
Teach. Assistance Coordinator (since Nov 20).
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 11).
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 11).

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

Program committee chair of

Program committee member of
Teach. Assistance Algorithms Lab (D-INFK) (Fall 11).

M. JAGGI
Teach. Assistance Graph Drawing (Spring 11).
Teach. Assistance Informatik I (D-MATH) (Fall 11).

V. KUSTERS
Teach. Assistance Algorithms, Probability, and Computing (D-INFK) (Fall 11).

R. MOSER
Coordinator Mittagsseminar (since Jun 23).
Teach. Assistance Datenstrukturen & Algorithmen (D-INFK) (Spring 11).
Contact Assistant Algorithms, Probability, and Computing (D-INFK) (Fall 11).

G. NIVASCH
Program committee member of

D. SCHEDER
Teach. Assistance Informatik (D-BIOL, D-PHARM) (Spring 11).

S. STICH
Webmaster www-gremo (since Oct 25).
Teach. Assistance Algorithms Lab (D-INFK) (Fall 11).

M. SULOVSKÝ
Coordinator Mittagsseminar (until Jun 22).

U. WAGNER
Program committee member of

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich, and member of the board of the Department of Computer Science, ETH Zurich.

Program committee member of

Editorial Board member of

Member (chair, contact person) of selection committees for

  • Assistant Professor for Risk and Insurance Economics, Department of Management, Technology, and Economics, ETH Zurich, (chair).

Member of the

  • Evaluation Panel of the Danish National Research Foundation Center MADALGO (Center for Massive Data Algorithmics), Aarhus University, Denmark (Jan 19-20, 2011).
  • Scientific Board of the Computer Science Department at Ecole normale supérieure (ENS), Paris, France.

Mitglied der Lehrkommission (ehemalige Studienkommission) der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.
Mitglied der Unterrichtskommission des Departements Informatik der ETH Zürich.


Software
23-Jan-2013 / stich@inf.ethz.ch