Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl
Quick~Links: 
Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Bachelor Theses, Miscellaneous, Software

Personnel

Professors
Gärtner, Bernd
Fukuda, Komei
Matoušek, Jiří
Welzl, Emo

Research Associates and Ph.D. Students
Hertli, Timon
Hoffmann, Michael, Dr.
Kusters, Vincent
Milatz, Malte (since Jul 1)
Mütze, Torsten, Dr. (since Oct 1)
Nummenpalo, Jerri (since Sep 1)
Stich, Sebastian (until Sep 30)
Szedlák, May
Thomas, Antonis
Tyagi, Hemant
Wettstein, Manuel

Administration
Salow, Andrea
Guests

Bartosz Walczak,
EPFL/Jagiellonian University, Kraków, Poland (Jan 21)
Online coloring games and the chromatic number of geometric intersection graphs
(Mittagsseminar, Jan 21, 2014)

Robin Moser, (Feb 1014)

Sonoko Moriyama,
Tohoku University, Sendai, Japan (Feb 2427)
Minimal nonorientable matroids of rank three
(Mittagsseminar, Feb 27, 2014)

Martin Jaggi (Mar 331)

Jerri Nummenpalo,
Aalto University, Finland (Apr 3)
Polytopal Big Data Statistics (Apr 3, 2014)

Micha Sharir,
Tel Aviv University, Israel (Apr 1220)
Algebraic techniques for incidence problems
(Mittagsseminar, Apr 15, 2014)

Malte Milatz,
RWTH Aachen, Germany (May 15)
Methods for Khovanov homology
(Mittagsseminar, May 15, 2014)

Lothar Narins,
FU Berlin, Germany (May 15  Jul 9)
The Connectedness of the Independence Complex of Line Graphs
(Mittagsseminar, May 22, 2014)

Zuzana Safernová,
Charles University, Prague, Czech Republic (Jun 9  Jul 4)
Bounds for Pach's selection theorem
(Mittagsseminar, Jun 10, 2014)

Imre Bárány,
Alfréd Rényi Mathematical Institute, Budapest, Hungary (Jun 1216)

Jean Cardinal,
Université Libre de Bruxelles, Brussels, Belgium (Jun 30  Jul 4)

Radoslav Fulek,
Columbia University, New York, USA (Jun 30  Jul 4)
Towards the HananiTutte Theorem for Clustered Graphs
(Combinatorial Algorithms Day, Jun 30, 2014)

Anna Gundert,
Universität zu Köln, Germany (Jun 30  Jul 4)
Generalizing Bipartiteness to Higher Dimensions
(Combinatorial Algorithms Day, Jun 30, 2014)

Tillmann Miltzow,
FU Berlin, Germany (Jun 30  Jul 4)

Yoshio Okamoto,
UEC Tokyo, Japan (Jun 30  Jul 4)
Extended Formulations for Sparsity Matroids
(Combinatorial Algorithms Day, Jun 30, 2014)

Andres Ruiz Vargas,
EPF Lausanne, Switzerland (Jun 30  Jul 4)
Disjoint Edges in Topological Graphs and the TangledThrackle Conjecture
(Combinatorial Algorithms Day, Jun 30, 2014)

Shakhar Smorodinsky,
BenGurion University, Be'er Sheva, Israel (Jun 30  Jul 4)
On Distinct Distances Between Points and Lines
(Combinatorial Algorithms Day, Jun 30, 2014)

József Solymosi,
University of British Columbia, Vancouver, Canada (Jun 30  Jul 4)
On extensions of the ElekesSzabó Theorem
(Combinatorial Algorithms Day, Jun 30, 2014)

Bettina Speckmann,
TU Eindhoven, The Netherlands (Jun 30  Jul 4)

Miloš Stojaković,
University of Novi Sad, Serbia (Jun 30  Jul 4)
Saturation Games on Graphs
(Combinatorial Algorithms Day, Jun 30, 2014)

Tibor Szabó,
FU Berlin, Germany (Jun 30  Jul 4)
On the Cycles of Degree3 Critical Graphs
(Combinatorial Algorithms Day, Jun 30, 2014)

Csaba Dávid Tóth,
California State University Northridge, California, USA (Jun 30  Jul 4)
Approximate Interior Barriers
(Combinatorial Algorithms Day, Jun 30, 2014)

Takeaki Uno,
National Institute of Informatics (NII), Tokyo, Japan (Jun 30  Jul 4)
Clustering by Iterative Graph Modification
(Combinatorial Algorithms Day, Jun 30, 2014)

Uli Wagner,
Institute of Science and Technology Austria, Klosterneuburg, Austria (Jun 30  Jul 4)
Eliminating Tverberg Points
(Combinatorial Algorithms Day, Jun 30, 2014)

Mary Inaba,
University of Tokyo, Japan (Jul 10  Jul 13)

Christian Müller
New York University, USA (Jul 1011)
Sparse model estimation and selection with the LASSO and the TREX in systems biology applications
(Mittagsseminar, Jul 11, 2014)

Yurii Nesterov,
Université Catholique de Louvain, Brussels, Belgium (Jul 11)

Alexander Pilz,
TU Graz, Austria (Aug 1822)

Micha Sharir,
Tel Aviv University, Israel (Aug 1922)

Luis Barba,
Carleton University / Université Libre de Bruxelles,
Canada / Belgium (Sep 1518)
Detecting intersections between convex polyhedra
(Mittagsseminar, Sep 16, 2014)

Jean Cardinal,
Université Libre de Bruxelles, Brussels, Belgium (Sep 30  Oct 3)
General Position Subsets in dspace
(Mittagsseminar, Oct 2, 2014)

Michael Kaufmann,
Universität Tübingen, Germany (Oct 6  8)

Matias Korman,
National Institute of Informatics, Tokyo, Japan (Oct 12  29)
Computing extremal distances in polygonal domains
(Mittagsseminar, Oct 14, 2014)

Luis Barba,
Carleton University / Université Libre de Bruxelles,
Canada / Belgium (Oct 27  30)

Uri Zwick,
Tel Aviv University,
Israel (Nov 36)

Michael Kaufmann,
Universität Tübingen, Germany (Dec 1  2)

Brian Cohn,
University of Southern California, USA (Dec 15  19)

Kazuo Iwama, Kyoto University, Japan (Dec 1617)
ReadOnce Branching Programs for Tree Evaluation Problems (Mittagsseminar, Dec 16, 2014)

Ramamohan Paturi,
University of California, San Diego, USA (Dec 16  18)
Grants

CrossingFree 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 crossingfree geometric graphsthese 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 crossingfree partitions), among others. A primary goal is to enumerate, count, or sample graphs of a certain type for a given point setso these are algorithmic questions, or to give estimates for the maximum and minimum number of such graphs on any set of n pointsthese are problems in extremal combinatorial geometry.
Contact: E. Welzl,
M. Wettstein

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 ValeroCuevas. 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 bioinformatics, 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, socalled 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, G. Aloupis, E. Demaine, M. Demaine, M. Hoffmann, S. Fekete, A. Lubiw, J. Snoeyink, A. Winslow,
Covering Folded Shapes,
Journal of Computational Geometry
, 5:1 (2014), 150168.
O. Aichholzer, J. Cardinal, Th. Hackl, F. Hurtado, M. Korman, A. Pilz, R. I. Silveira, R. Uehara, B. Vogtenhuber, E. Welzl,
CellPaths in Mono and Bichromatic Line Arrangements in the Plane,
Discrete Mathematics & Theoretical Computer Science
(2014), to appear.
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), 4769.
A. Baertschi, S. Suri,
Conflictfree chromatic art gallery coverage,
Algorithmica 68:1 (2014), 265283.
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. (2014), to appear.
B. Bukh, J. Matoušek,
ErdősSzekerestype statements: Ramsey function and decidability in dimension 1,
Duke Mathematical Journal 163:12 (2014), 22432270.
M. Čadek, M. Krčál, J. Matoušek, L. Vokřínek, U. Wagner,
Extendability of continuous maps is undecidable,
Discrete & Computational Geometry 51:1 (2014), 2466.
M. Čadek, M. Krčál, J. Matoušek, L. Vokřínek, U. Wagner,
Polynomialtime computation of homotopy groups and Postnikov systems in fixed dimension,
SIAM J. Computing (2014), 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 61:3 (2014), Article No.: 17.
D. Clemens, H. Gebauer, A. Liebenau,
The random graph intuition for the tournament game, Combinatorics, Probability and Computing (2015), to appear.
M. Elias, J. Matoušek, E. RoldánPensado, Z. Safernová,
Lower bounds on geometric Ramsey functions,
SIAM J. Discrete Math. 28:4 (2014), 19601970.
J. Foniok, B. Gärtner, L. Klaus, M. Sprecher,
Counting UniqueSink Orientations,
Discrete Applied Mathematics
163:2 (2014), 155164.
F. Frati, J. Gudmundsson, E. Welzl,
On the Number of Upward Planar Orientations of Maximal Planar Graphs,
Theoretical Computer Science 544
(2014), 3259.
B. Gärtner,
Sampling with Removal in LPtype Problems,
Journal of Computational Geometry (JoCG) (2014), to appear.
X. Goaoc, J. Matoušek, P. Paták, Z. Safernová, M. Tancer,
Simplifying inclusionexclusion formulas,
Combinatorics, Probability and Computing (2014), to appear.
T. Hertli,
3SAT Faster and Simpler  UniqueSAT Bounds for PPSZ Hold in General,
SIAM Journal of Computing
43:2 (2014), 718729.
M. Hoffmann and Cs.D. Tóth,
VertexColored Encompassing Graphs,
Graphs and Combinatorics 30:4 (2014), 933947.
J. Matoušek,
Nearoptimal separators in string graphs,
Combinatorics, Probability and Computing 23:1 (2014), 135139.
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.
J. Matoušek, U. Wagner,
On Gromov's method of selecting heavily covered points,
Discrete and Computational Geometry 52:1 (2014), 133.
A. Thomas, J. van Leeuwen,
Pure Nash Equilibria in Graphical Games and Treewidth, Algorithmica
(2014), to appear.
H. Tyagi, V. Cevher,
Learning nonparametric basis independent models from point queries via lowrank methods,
Applied and Computational Harmonic Analysis 37:3 (2014), 389412.
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)
O. Aichholzer, J. Cardinal, V. Kusters, S. Langerman, P. Valtr,
Reconstructing Point Set Order Types from Radial Orderings,
Proc. 25th International Symposium on Algorithms and Computation (ISAAC) (2014), to appear.
I. Bárány, J. Matoušek, A. Por,
Curves in R^{d} intersecting every hyperplane at most d+1 times,
Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 565574.
K. Buchin, A. van Goethem, M. Hoffmann, M. van Kreveld, B. Speckmann.
Traveltime Maps: Linear Cartograms with Fixed Vertex Locations,
Proc. 8th International Conference on Geographic Information Science (GIScience)
(2014) LNCS 8728, 1833.
M. Elias, J. Matoušek, E. RoldánPensado, Z. Safernová,
Lower bounds on geometric Ramsey functions,
Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 558564.
W. Evans, V.Kusters, M. Saumell, B. Speckmann,
Column Planarity and Partial Simultaneous Geometric Embedding,
22nd International Symposium on Graph Drawing (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), 242250.
B. Gärtner,
Sampling with Removal in LPtype Problems,
Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 511518.
B. Gärtner, A. Krause, H. Tyagi,
Efficient Sampling for Learning Sparse Additive Models in High Dimensions,
Advances in Neural Information Processing Systems (NIPS) (2014), 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.
B. Gärtner, H. Tyagi,
Continuum armed bandit problem of few variables in high dimensions,
Proc. 11th Workshop on Approximation and Online Algorithms (WAOA) (2014) LNCS 8447, 108119.
X. Goaoc, J. Matoušek, P. Paták, Z. Safernová,
Simplifying inclusionexclusion 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), 181188.
T.Hertli,
Breaking the PPSZ Barrier for Unique 3SAT,
41st International Colloquium on Automata, Languages and Programming (ICALP) (2014) LNCS 8572, 600611.
M. Hoffmann, V. Kusters, T. Miltzow,
Halving Balls in Deterministic Linear Time,
Proc. 22nd Annual European Symposium on Algorithms (ESA) (2014) LNCS 8737, 566578.
J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner,
Embeddability in the 3sphere is decidable,
Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 7887.
S. Stich,
On low complexity Acceleration Techniques for Randomized Optimization,
13th International Conference on Parallel Problem Solving From Nature (PPSN) (2014) LNCS 8672, 130140.
M. Wettstein,
Counting and Enumerating Crossingfree Geometric Graphs,
Proc. 30th Annual ACM Symposium on Computational Geometry (SoCG) (2014), 110.

Other (including submitted work)
O. Aichholzer, Th. Hackl, M. Korman, M. van Kreveld, M. Löffler, A. Pilz, B. Speckmann, E. Welzl,
Packing Plane Spanning Trees and Paths in Complete Geometric Graphs,
Proc. 26th Canadian Conference on Computational Geometry (CCCG) (2014), 6 pages.
O. Aichholzer, M. Hoffmann, M. van Kreveld, G. Rote,
Graph Drawings with Relative Edge Length Specifications
Proc. 26th Canadian Conference on Computational Geometry (CCCG) (2014), 7 pages.
Y. Brise, K. Buchin, D. Eversmann, M. Hoffmann, W. Mulzer,
Interference Minimization in Asymmetric Sensor Networks,
Proc. 10th International Symposium on Algorithms and Experiments
for Sensor Systems (ALGOSENSORS) (2014), 16 pages.
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,
Threemonotone 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.
M. Hoffmann, M. van Kreveld, V. Kusters, G. Rote,
Quality Ratios of Measures for Graph Drawing Styles,
Proc. 26th Canadian Conference on Computational Geometry (CCCG) (2014), 7 pages.
M. Hoffmann, V. Kusters, T. Miltzow,
Separating Balls with a Hyperplane,
Abstracts of the 30th European Workshop on Computational Geometry (EuroCG), EinGedi, Israel (2014).
V. Kusters, B. Speckmann,
Characterizing Graphs With A Sliceable Rectangular Dual,
(2013), submitted.
J. Matoušek,
String graphs and separators (expository paper), in J. Matoušek, J. Nesetril, M. Pellegrini (eds.): Geometry, Structure and Randomness in Combinatorics, CRM Series, Springer, (2014).
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
T. HERTLI
"Breaking the PPSZ Barrier for Unique 3SAT", CSE Theory Seminar, UC San Diego, USA (Jan 27, 2014).
M. HOFFMANN
"Graph Drawings with Relative Edge Length Specifications", 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax, Nova Scotia, Canada (Aug 12, 2014).
V. KUSTERS
"Planar Packing of Binary Trees",
EuroGIGA Final Conference, Freie Universität Berlin, Germany (Feb 18, 2014).
"Column Planarity and Partial Simultaneous Geometric Embedding",
Graph Drawing 2014, University of Würzburg, Germany (Sep 25, 2014; best presentation award).
S. STICH
"Probabilistic Estimate Sequences",
TAO research seminar, INRIA Saclay,
ÎledeFrance, France (Mar 25, 2014).
"Probabilistic Estimate Sequences",
8th workshop on Theory of Randomized Search Heuristics (ThRaSH 2014)
Jena, Germany (Apr 4, 2014).
"Randomized Methods in Optimization",
8th Zurich Machine Learning and Data Science Meetup, Zurich, Switzerland (Sep 30, 2014).
M. SZEDLÁK
"Higher dimensional discrete Cheeger inequalites", Oberseminar, University of Cologne, Germany (May 7 2014).
A. THOMAS
"Recognizability & Long Cycles in USOs", COGA Breakfast Seminar, TU Berlin, Germany (Aug 26, 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 CrossingFree Geometric Graphs  Algorithms and Combinatorics",
PreWorkshop (WALCOM) School on Algorithms and Combinatorics,
IIT Chennai, India (Feb 10, 2014).
"The Counting of CrossingFree Geometric Graphs  Algorithms and Combinatorics”,
Summit 240 Conference, Alfréd Rényi Institute of Mathematics,
Budapest, Hungary (Jul 10, 2014; invited plenary talk).
M. WETTSTEIN
"Counting and Enumerating Crossingfree Perfect Matchings",
EuroGIGA Final Conference, Freie Universität Berlin, Germany (Feb 21, 2014).
"Counting and Enumerating Crossingfree Geometric Graphs",
JapaneseSwiss Workshop on Combinatorics and Computational Geometry, University of Tokyo, Japan (Jun 4, 2014).
"Counting and Enumerating Crossingfree Geometric Graphs",
30th Annual Symposium on Computational Geometry (SoCG), University of Kyoto, Japan (Jun 8, 2014).
Courses and Seminars
Spring 15

Data Structures and Algorithms,
J. Matoušek, P. Widmayer; (VL Th0810 HG G 5, Th1012 HG G 5; UE We1517, We1618), contact assistant: Tobias Pröger.

Polyhedral Computation,
K. Fukuda; (VL Tu1517 CHN D 48, UE Tu1718 CHN D 48),
contact assistant: May Szedlák.

Satisfiability of Boolean Formulas  Combinatorics and Algorithms,
E. Welzl;
(VL Tu1012 CAB G59, Th910 CAB G59, UE Tu1315 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 Tu1213 CAB G51, Th1213 CAB G51).

Seminar Geometry: Combinatorics and Algorithms,
B. Gärtner, M. Hoffmann, E. Welzl;
(SE Fr1315 CAB G15.2).

Seminar: Wie funktioniert Forschung? Algorithmen und Kombinatorik,
B. Gärtner, J. Matoušek, A. Steger, E. Welzl, P. Widmayer;
(SE Tu1517 CAB G15.2).
Fall 14

Algorithms Lab,
A. Steger, E. Welzl, P. Widmayer;
(VL We1719 CAB G61, UE Mo1719, [+1A]),
contact email: algolab@lists.inf.ethz.ch.

Algorithms, Probability, and Computing,
E. Welzl, T. Holenstein, P. Widmayer;
(VL Mo1315 CAB G51, Tu1416 CAB G51; UE We1315 CAB G56, We1315 CHN D44, We1618 CAB G52 [+1A]),
contact assistant: Manuel Wettstein.

Diskrete Mathematik (DITET),
J. Lengler, E. Welzl;
(VL Mo1012 NO C60, UE Fr1012 biweekly)
contact assistant: Karl Bringmann.

Geometry: Combinatorics and Algorithms,
B. Gärtner, M. Hoffmann, E. Welzl;
(VL Th1315 CAB G51, UE Th1517 ML H41.1, [+1A]),
contact assistant: Hemant Tyagi.

Informatik (DMATH, DPHYS),
B. Gärtner;
(VL Tu1315 ML D28/E12, UE Tu1517),
contact assistant: Christian Zingg.

Theory of Computing (Theoretische Informatik),
J. Hromkovic, E. Welzl;
(VL Tu810 CAB G61, Fr810 CAB G61, UE We1315, UE Th1618)
contact assistant: Dr. HansJoachim Böckenhauer.

Seminar in Combinatorics: Mathematical Software,
K. Fukuda;
(SE Tu1012 HG E33.3).

Seminar on Optimization and Applications,
R. Weismantel, B. Gärtner, D. Klatte, J. Lygeros, M. Morari, K. Schmedders, R. Smith, R. Zenklusen;
(K Mo1618 HG G19.1).

Seminar SAT,
E. Welzl; contact assistant: Timon Hertli.
(SE Fr1012 CAB G57).

Seminar der Theoretischen Informatik (Mittagsseminar),
A. Steger, E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler;
(SE Tu1213 CAB G51, Th1213 CAB G51).
Spring 14

Optimization and Applications Seminar,
B. Gärtner, D. Klatte, J. Lygeros, M. Morari, K. Schmedders, R. Smith, R. Weismantel, R. Zenklusen;
(K Mo1618 HG G19.1).

Polyhedral Computation,
K. Fukuda; (VL Tu1517 HG E1.1, UE Tu1718 HG E1.1),
contact assistant: May Szedlák.

Polynomials,
J. Matoušek; E. Welzl;
(VL Mo1012 CAB G57, UE Mo 1314 CAB G57),
contact assistant: Vincent Kusters.

Satisfiability of Boolean Formulas  Combinatorics and Algorithms,
E. Welzl;
(VL Tu1012 CAB G51, Th910 CAB G59, UE Fr1012 CAB G51, [+1A]),
contact assistant: Timon Hertli.

Seminar der Theoretischen Informatik (Mittagsseminar),
B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov, E. Welzl;
(SE Tu1213 CAB G51, Th1213 CAB G51).

Seminar: Wie funktioniert Forschung? Algorithmen und Kombinatorik,
B. Gärtner, J. Matoušek; A. Steger, E. Welzl, P. Widmayer;
(SE Tu1517 CAB G15.2).
Organization of Workshops etc.

12th Gremo Workshop on Open Problems 2014,
Val Sinestra (GR), Switzerland,
Jun 30  Jul 4, 2014,
(Michael Hoffmann).

International Workshop on Algorithms and Computation (WALCOM 2014) PreWorkshop School on Algorithms and Combinatorics,
Indian Institute of Technology, Madras, India,
Feb 13  15, 2014,
(John Augustine, Subir Ghosh, Emo Welzl, B. V. Raghavendra Rao, Swami Sarvottamananda, Partha Goswami).

JapaneseSwiss Workshop on Combinatorics and Computational Geometry
University of Tokyo, Japan, Jun 4  6, 2014, (Komei Fukuda).
Dissertations

Sebastian Stich,
Convex Optimization with Random Pursuit
Advisor: Bernd Gärtner (referee) / Coreferees: Yurii Nesterov, Université catholique de Louvain, Christian L. Müller, New York University, Emo Welzl, ETH Zürich / Defense: Jul 11, 2014.
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

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 / to be completed

Luca Eggemann,
A View of Triangulations as Maximal Cliques,
Advisor: Emo Welzl / 8.5.2014

Qinheping Hu,
Survey on Partial Satisfaction,
Advisors: Timon Hertli, Emo Welzl / 22.8.2014

Patrick Schnider,
Shortest Paths in Disk Coverings,
Advisors: Michael Hoffmann, Torsten Mütze / 1.1.2014

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.
Teach. Assistance Satisfiability of Boolean Formulas  Combinatorics and Algorithms (DINFK) (Spring 14).
Teach. Assistance Informatik (DMATH, DPHYS) (Fall 2014).
M. HOFFMANN
Informatik Koordinator.
Teach. Assistance Algorithms Lab (DINFK) (Fall 14).
Member of the CGAL Editorial Board.
Program committee member of
V. KUSTERS
Coordinator Mittagsseminar.
Teach. Assistance Polynomials (DINFK) (Spring 14).
Teach. Assistance Algorithms, Probability, and Computing (DINFK) (Fall 14).
J. MATOUŠEK
Elected member of the
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).
Program committee member of
Juror for the RichardRadoPrize 2014 of the Fachgruppe Diskrete Mathematik
of the German Mathematical Society (DMV), awarded at the GoetheUniversität
Frankfurt am Main, May 2014.
M. MILATZ
Teach. Assistance Algorithms, Probability, and Computing (DINFK) (Fall 2014).
S. STICH
Webmaster wwwgremo (until Sep 30, 2014).
Program committee member of
M. SZEDLÁK
Teach. Assistance Polyhedral Computation (DMATH) (Spring 14).
Teach. Assistance Algorithms, Probability, and Computing (DINFK) (Fall 14).
A. THOMAS
Teach. Assistance Algorithms Lab (DINFK) (Fall 14).
Teach. Assistance Informatik (DMATH, DPHYS) (Fall 2014).
H. TYAGI
Webmaster wwwgremo (since Oct 1, 2014).
Teach. Assistance Data Mining: Learning from Large Data Sets (DINFK) (Spring 14).
Contact Assistant Geometry: Combinatorics and Algorithms (DINFK) (Fall 14).
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/PlantMicrobial 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 24, 2014).
Delegierter für Professorenwahlen an der ETH Zürich.
Elected as a corresponding member to the Austrian Academy of Sciences (OeAW).
M. WETTSTEIN
Contact Assistant Algorithms, Probability, and Computing (DINFK) (Fall 14).
Software
