Department of Computer Science

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

Topics for Master / Bachelor Theses

CGAL Geometric Algorithms Library
  Activity Report 2014

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



Grants


  • 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

  • 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


Publications


  • Books

  • Journals (with refereeing)

    O. Aichholzer, T. Hackl, M. Hoffmann, A. Pilz, G. Rote, B. Speckmann, B. Vogtenhuber, Plane Graphs with Parity Constraints, Graphs and Combinatorics, 30:1 (2014), 47-69.

    A. Baertschi, S. Suri, Conflict-free chromatic art gallery coverage, Algorithmica 68:1 (2014), 265-283.

    B. Bukh, J. Matoušek, Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1, Duke Mathematical Journal (2013), to appear.

    M. Čadek, M. Krčál, J. Matoušek, L. Vokřínek, U. Wagner, Extendability of continuous maps is undecidable, Discrete & Computational Geometry (2013), to appear.

    M. Čadek, M. Krčál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Computing all maps into a sphere, Journal of the ACM (2013), to appear.

    J. Foniok, B. Gärtner, L. Klaus, M. Sprecher, Counting Unique-Sink Orientations, Discrete Applied Mathematics 163:2 (2014), 155-164.

    F. Frati, J. Gudmundsson, E. Welzl, On the Number of Upward Planar Orientations of Maximal Planar Graphs, Theoretical Computer Science (2014), to appear.

    T. Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General, SIAM Journal of Computing (2013), to appear.

    M. Hoffmann and Cs.D. Tóth, Vertex-Colored Encompassing Graphs Graphs and Combinatorics (2013), to appear.

    J. Matoušek, Near-optimal separators in string graphs, Combinatorics, Probability and Computing, 23:1 (2014), 135-139.

    J. Matoušek, U. Wagner, On Gromov's method of selecting heavily covered points, Discrete and Computational Geometry (2012), to appear.

    H. Tyagi, V. Cevher, Learning non-parametric basis independent models from point queries via low-rank methods, Applied and Computational Harmonic Analysis (2014), to appear.

  • Conference Proceedings (with selection process)

    I. Bárány, J. Matoušek, A. Por, Curves in Rd intersecting every hyperplane at most d+1 times, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), to appear.

    M. Elias, J. Matoušek, E. Roldán-Pensado, Z. Safernová, Lower bounds on geometric Ramsey functions, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), to appear.

    A. Francke, Cs.D. Tóth, A Census of Plane Graphs with Polyline Edges, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), to appear.

    B. Gärtner, Sampling with Removal in LP-type Problems, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), to appear.

    B. Gärtner, H. Tyagi, Continuum armed bandit problem of few variables in high dimensions, 11th Workshop on Approximation and Online Algorithms (WAOA) (2013), to appear.

    X. Goaoc, J. Matoušek, P. Paták, Z. Safernová, Simplifying inclusion-exclusion formulas, European Conference on Combinatorics, Graph Theory and Applications (Eurocomb) (2013), to appear.

    A. Gundert, M. Szedlák, Higher Dimensional Discrete Cheeger Inequalities, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), to appear.

    T.Hertli, Breaking the PPSZ Barrier for Unique 3-SAT, 41st International Colloquium on Automata, Languages and Programming (ICALP) (2014), to appear.

    J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Embeddability in the 3-sphere is decidable, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), to appear.

    M. Wettstein, Counting and Enumerating Crossing-free Geometric Graphs, Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), to appear.

  • Other (including submitted work)

    M. Čadek, M. Krčál, J. Matoušek, L. Vokřínek, U. Wagner, Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension, (2012), submitted.

    D. Clemens, H. Gebauer, A. Liebenau, The random graph intuition for the tournament game, (2013), submitted.

    K. Fukuda, L. Klaus, H. Miyata, Enumeration of PLCP-orientations of the 4-cube, (2013), submitted.

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

    M. Hoffmann, V. Kusters, T. Miltzow, Separating Balls with a Hyperplane, Abstracts of the 30th European Workshop on Computational Geometry (EuroCG), Ein-Gedi, Israel (2014).

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

    A. Thomas, J. van Leeuwen, Pure Nash Equilibria in Graphical Games and Treewidth, (2013), submitted.

    H. Tyagi, S. Stich, B. Gärtner, On two continuum armed bandit problems in high dimensions, (2014), submitted.

    H. Tyagi, S. Stich, B. Gärtner, Stochastic continuum armed bandit problem of few linear parameters in high dimensions, (2014).


Lectures


T. HERTLI
"Breaking the PPSZ Barrier for Unique 3-SAT", CSE Theory Seminar, UC San Diego, USA (Jan 27, 2014).

V. KUSTERS
"Planar Packing of Binary Trees", EuroGIGA Final Conference, Freie Universität Berlin, Germany (Feb 18, 2014).

S. STICH
"Probabilistic Estimate Sequences", TAO reserach seminar, INRIA Saclay, Île-de-France, France (Mar 25, 2014).
"Probabilistic Estimate Sequences", 8th workshop on Theory of Randomized Search Heuristics (ThRaSH 2014) Jena, Germany (Apr 4, 2014).

E. WELZL
"When Conflicting Constraints can be Resolved - the Local Lemma and Satisfiability ", The Institute Colloquium, Institute of Science and Technology (IST Austria), Klosterneuburg, Maria Gugging, Austria (Jan 13, 2014).
"The Counting of Crossing-Free Geometric Graphs - Algorithms and Combinatorics", Pre-Workshop (WALCOM) School on Algorithms and Combinatorics, IIT Chennai, India (Feb 10, 2014).

M. WETTSTEIN
"Counting and Enumerating Crossing-free Perfect Matchings", EuroGIGA Final Conference, Freie Universität Berlin, Germany (Feb 21, 2014).

Courses and Seminars


Spring 14

See also the Course Catalogue

Fall 13

See also the Course Catalogue


Organization of Workshops etc.



Dissertations



Master Theses


  • Isabelle Hurbain, Towards a Derandomization of the PPSZ Algorithm for Multiple Satisfying Assignments,
    Advisor: Timon Hertli / 31.3.2014

Bachelor and Semester Theses / Internship Projects


  • Stephan Ammann, Draw an outerplanar graph and a matching at the same time,
    Advisors: Michael Hoffmann, Vincent Kusters / start in February 2014
  • Luca Eggemann, A View of Triangulations as Maximal Cliques,
    Advisor: Emo Welzl / to be completed
  • Patrick Schnider, Shortest Paths in Disk Coverings,
    Advisors: Michael Hoffmann, Torsten Mütze / 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.
Teach. Assistance Satisfiability of Boolean Formulas - Combinatorics and Algorithms (D-INFK) (Spring 14).

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

Program committee member of

V. KUSTERS
Coordinator Mittagsseminar.
Teach. Assistance Polynomials (D-INFK) (Spring 14).

J. MATOUŠEK
Elected member of the

Editorial Board member of

Program committee member of

S. STICH
Webmaster www-gremo.

Program committee member of

M. SZEDLÁK
Teach. Assistance Polyhedral Computation (D-MATH) (Spring 14).

H. TYAGI
Teach. Assistance Data Mining: Learning from Large Data Sets (D-INFK) (Spring 14).

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).
  • Professor of Applied Mathematics, Department of Mathematics, ETH Zurich, (chair).
  • Professor of Biological Systems Theory, Department of Biosystems Science and Engineering, ETH Zurich, (chair).
  • Professor of Computer Science, Computer Science Department, Ecole normale superieure (ENS), Paris, France.
  • 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

Program committee member of

  • 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT `14), Copenhagen, Denmark (July 2-4, 2014).

Member of ETH Quality Audit Preparation Chapter Review Group "Personal".
Delegierter für Professorenwahlen an der ETH Zürich.


Software


20-Mar-2014 / stich@inf.ethz.ch