Personnel

• Professors

  Fukuda, Komei (1/3 appointment)
  Welzl, Emo

• Research Associates and Ph.D. Students

  Berke, Robert (until Sep 12)
  Brise, Yves
  Christ, Tobias
  Gärtner, Bernd, Dr.
  Gebauer, Heidi
  Hoffmann, Michael, Dr.
  Jaggi, Martin
  Moser, Robin (since Jan 15)
  Razen, Andreas
  Sankowski, Piotr, Dr. (until Aug 31)
  Scheder, Dominik
  Sulovský, Marek
  Szabó, Tibor, Dr. (until Aug 31)
  Traxler, Patrick
  Wagner, Uli, Dr.
  Zumstein, Philipp
  

• Administration

  Salow, Andrea
  

Guests

• Miloš Stojakovíc, Department of Mathematics and Computer Science, University of Novi Sad, Novi Sad, Serbia (Jan 28 - Feb 7)
  Slow losing again (Mittagsseminar, Feb 5, 2008)
• Joachim Giesen, Max-Planck-Institut für Informatik, Saarbrücken, Germany (Feb 5 - Feb 15)
  The solution path of the slab SVM (Mittagsseminar, Feb 12, 2008)
• Martin Tancer, Charles University, Prague, Czech Republic (Mar 12 - May 30)
  On the complexity of recognition of d-collapsible complexes (Mittagsseminar, May 6, 2008)
• Jiří Matoušek, Department of Applied Mathematics, Charles University, Prague, Czech Republic (Apr 3 - Jul 20)
  On the difficulty of removing degeneracy in LP-type problems: The way of topology (Mittagsseminar, May 8, 2008)
  Low-distortion embeddings in R^d (Mittagsseminar, May 27, 2008)
• Gábor Fejes Tóth, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary (May 1 - Jun 30)
  
• Eran Nevo, Cornell University, Ithaca NY, USA (May 19 - 27)
  A characterization of simplicial polytopes with g_2=1 (Mittagsseminar, May 22, 2008)
• Nathan (Nati) Linial, The Hebrew University of Jerusalem, Israel (May 8 - 10)
  Recent Progress on Eigenvalues and Eigenfunctions of Graphs (Computer Science Colloquium, May 8, 2008)
• Anastasios Sidiropoulos, Massachusetts Institute of Technology, Boston, USA (May 19 - 23)
  Circular Partitions with Applications to Visualization and Embeddings (Mittagsseminar, May 20, 2008)
• Karl J. Lieberherr, Northeastern University, Boston, USA (Jul 8)
  Using Artificial Markets to Teach Computer Science Through Trading Robots (Mittagsseminar, Jul 8, 2008)
• Joachim Giesen, Max-Planck-Institut für Informatik, Saarbrücken, Germany (Aug 21 - 26)
• Alexander Gamkrelidze, Saarland University, Saarbrücken, Germany (Sep 8 - 12)
  
• Yoshio Okamoto, Tokyo Institute of Technology, Japan (Sep 8 - 12)
  Adaptive computational geometry (Combinatorial Algorithms Day, Sep 10, 2008)
• Shakhar Smorodinsky, Ben-Gurion University, Be'er Sheva, Israel (Sep 8 - 12)
  Conflict-Free coloring made stronger (Combinatorial Algorithms Day, Sep 10, 2008)
• Miloš Stojakovíc, Department of Mathematics and Computer Science, University of Novi Sad, Novi Sad, Serbia (Sep 8 - 12)
  Positive min-degree game on sparse graphs (Combinatorial Algorithms Day, Sep 10, 2008)
• Raimund Seidel, Saarland University, Saarbrücken, Germany (Oct 4 - 7)
  Making the Inverse Ackermann Function Appear Natural(ly) (Mittagsseminar, Oct 7, 2008)
• Tom Rackham, Oxford University, UK (Nov 10 - 13),
  Methods of distance-constraint precolouring (Mittagsseminar, Nov 11, 2008)
• Nicolai Hähnle, EPFL, Lausanne (Nov 24-25)
  Combinatorial abstractions for the diameter of polyhedra (Optimization and Applications Seminar, Nov 24, 2008)
• Rom Pinchasi, Technion, Israel (Dec 15-16)
  Some new results related to the 'halving lines problem' (Mittagsseminar, Dec 16, 2008)

Grants

• 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: Bernd Gärtner

• Boolean Satisfiability - Combinatorics and Algorithms

  (Financed by the Swiss National Science Foundation.) SAT is the problem of deciding whether a boolean formula in propositional logic is satisfiable, i.e. whether there is a true/false assignment to the boolean variables so that the given formula evaluates to true. The problem is of importance in various areas of computer science, including algorithmics, artificial intelligence, and program and system verification. Frequently, problems are modeled as SAT instances, and SAT-solvers like Mini-SAT, zCHAFF, HaifaSAT, etc. are used to solve such instances.

  This project concentrates on the theoretical aspects of the problem, which plays a key role in theoretical computer science for several reasons, one being that it is considered the `mother' of NP-complete problems. The goal of the project is to obtain a deeper understanding of the computational complexity of SAT and the structural properties of CNF formulas.

  Contact: E. Welzl, D. Scheder, P. Traxler, P. Zumstein

• Geometric, Algebraic, and Topological Invariants for k-Facets and Levels in Arrangements

  (Financed by the Swiss National Science Foundation.) The goal of the proposed project is to study levels in arrangements of halfspaces and hemispheres, respectively the dual notions of k-sets and k-facets of finite point sets in real affine d-space. In its simplest, 2-dimensional form, the basic problem can be stated as follows: Given n points in the plane and a parameter k, 0<k<n, how many ways are there to divide them into two equal parts by a straight line, such that k points lie on one side of the line, and n-k points on the other side? A subset of k points that can be separated in this way from the remaining n-k points is called a k-set of the point set. The number of k-sets depends on the particular placement of the poinst, and the goal is to determine the maximum number of k-sets, for any placement of n points, in terms of n and k. This is a long-standing open question in discrete and computational geometry, and despite 35 years of research and numerous partial results, there remains a wide gap between the upper and lower bounds proved to date.
  The scope of this project is threefold. The first part concerns the interplay between k-sets and levels in arrangements on the one hand and the theory of face numbers of convex polytopes and algebraic combinatorics on the other hand. The main focus are h-matrices of linear programs (a generalization of h-vectors of convex polytopes) and its geometric and algebraic interpretations.
  The second part concerns the study of invariants for k-facets in low dimensions, specifically extensions and analogues of the crossing identity for planar k-sets in terms of topological invariants of plane curves, such as Arnold's basic invariants.
  The third part concerns applications, e.g. to the rectilinear crossing number of complete graphs, and generalizations of k-sets, such as crossing-free partitions.

  Contact: U. Wagner

• Games and Geometric Unique Sink Orientations

  (Financed by the Swiss National Science Foundation.) In the first part of the project, we will be dealing with combinatorial structure in games and matrix classes. This is motivated by the recent research that links certain well-studied classes of games to exactly the abstract combinatorial models we were studying in the project Combinatorial Models for Geometric Optimization. This research concerns the classes of simple stochastic games, mean payoff games and parity games.
  The second part of the project deals with specific unique sink orientations (USO) arising from geometric applications. Within the former project Combinatorial Models for Geometric Optimization, we have shown that a USO is hidden behind any linear program (LP), and that this USO has a special property: it satisfies the Holt-Klee condition, a combinatorial condition concerned with directed paths in the USO. We call such a USO geometric.

  Contact: B. Gärtner, T. Szabó

• Algorithms for Complex Shapes with Certified Numerics and Topology (ACS)

  (European Project.) Increasingly demanding applications of geometric computing, for example in CAD/CAM, computer aided surgery, realistic virtual environments, robotics, and molecular modeling in drug design and structural biology, require efficient and robust methods for computing with complex shapes. This project aims at advancing the state of the art in this field. Current technology can cope well with curves in the plane and smooth surfaces in three-dimensional space. We want to deal with a larger class of shapes, including piecewise smooth and singular surfaces.
  Topics that we address are shape approximation (including meshing and simplification), shape learning (including reconstruction and feature extraction), as well as robust modeling (including boolean operations). Our work on these topics will be closely intertwined with basic research on shape representations, certified geometric calculus and algorithms producing output with guaranteed topology.
  A distinctive feature is the design and implementation of novel algorithmic solutions with certified topology and numerics as an alternative for heuristics and ad hoc methods, and the development of an experimental geometry kernel for modeling and computing with complex shapes as a proof-of-concept justifying our approach. The results of this project should be directly useful to the application areas mentioned above. We intend to disseminate our work by publication in the appropriate applied research forums, by organizing multidisciplinary workshops aimed at exchange of knowledge and discussion of our work. Moreover, we aim at transferring our new technology by producing high quality software, demonstrating the feasibility of our techniques in practice. Cooperation with our industrial partner includes the assessment, trial, validation and packaging of the software developed in the project, thus guaranteeing a smooth transfer of new technology to application areas.
  At ETH, we focus on new geometric data structures and optimization-based primitives to deal with shapes, and we provide according software components, building on our experience with reconstruction and optimization software for various tasks.

  Contact: B. Gärtner, J. Giesen

• Polytopes, Matroids and Polynomial Systems - Studies through the Fusion of Geometric, Combinatorial and Algebraic Algorithms

  (Financed by the Swiss National Science Foundation.) This project concerns research themes that interlink four domains in mathematics: combinatorics, algebra, geometry and optimization. We address fundamental questions and applications that rely crucially on this fusion.
  Our strong drive for this fusion of the established research domains comes from the observation that several fundamental problems spreading over these domains are closely interlinked: a solution to one of the problems often leads to a solution for another one in a different domain. More precisely, we propose to study the following four specific research themes (with its principal domain).

  1. Classifications of Oriented Matroids (Combinatorics)
  2. State Polytopes of Polynomial Ideals (Algebra)
  3. Minkowski Addition of Polytopes and Convex Hull (Geometric Computation)
  4. Solving Polynomial Systems and SDPs via Structure Information (Optimization)
  
  Each of the four themes has a long history of earlier investigations in its principal domain. With these themes studied extensively for many years, it is becoming increasing evident that these four themes are closely related and inseparable.
  In fact, there are underlying mathematical structures, convex polytopes, matroids and polynomials common to all these themes. Our belief is that it makes much more sense to investigate them together. Our research team consists of active researchers, each with at least two domains of competence and strong interests in making this nontrivial fusion.

  Contact: E. Feichtner, ETHZ, K. Fukuda, ETHZ and EPFL, P. Parrilo, ETHZ, and R. Thomas, University of Washington

Publications

• Books

• Journals (with refereeing)

  P. Agarwal, M. Sharir, E. Welzl, Algorithms for center and Tverberg points, ACM Transactions on Algorithms 5(1) (2008), Article 5 (20 pp.).

  V. Anuradha, C. Jain, J. Snoeyink, T. Szabó, How long can a graph be kept planar? Electronic Journal of Combinatorics, 15(1) (2008), N14.

  K. Buchin, T.K. Dey, J. Giesen and M. John, Recursive Geometry of the Flow Complex and Topology of the Flow Complex Filtration, Computational Geometry - Theory and Applications 40 (2008), 115-137.

  T.K. Dey, J. Giesen, E. Ramos and B. Sadri, Critical points of the distance to an epsilon-sampling of a surface and flow based surface reconstruction, International Journal of Computational Geometry and Applications 18 (2008), 29-61.

  B. Gärtner, J. Matoušek, L. Rüst, P. Škovroň, Violator spaces: structure and algorithms, Discrete Applied Mathematics 156:11 (2008), 2124-2141.

  B. Gärtner, W. D. Morris Jr., L. Rüst, Unique sink orientations of grids, Algorithmica 51:2 (2008) 200-235.

  D. Hefetz, M. Krivelevich, M. Stojakovic, T. Szabó, Planarity, colorability and minor games, SIAM Journal on Discrete Mathematics, 22 (2008), 194-212.

  M. Krivelevich, T. Szabó, Large covers of hypergraphs and biased positional games, Electronic Journal of Combinatorics, 15(1) (2008), R70.

  J. Matoušek, LC reductions yield isomorphic simplicial complexes, Contributions to Discrete Mathematics (electronic) 3,2 (2008), 37-39.

  J. Matoušek, On variants of the Johnson--Lindenstrauss lemma, Random Structures & Algorithms 33:2 (2008), 142-156.

  U. Wagner, k-Sets and k-Facets, Discrete & Computational Geometry - 20 Years Later, AMS Series Contemporary Mathematics (2008), 443-513.

• Conference Proceedings (with selection process)

  N. Alon, R. Berke, K. Buchin, M. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, P. Zumstein, Polychromatic Coloring of Plane Graphs, Proc. 24th Annual ACM Symposium on Computational Geometry (SoCG) (2008), 338-345.

  T. Christ, M. Hoffmann, Y. Okamoto, T. Uno, Improved Bounds for Wireless Localization, Proc. 11th Scandinavian Workshop on Algorithm Theory (SWAT) (2008), 77-89.

  J. Díaz, D. Mitsche, X. Pérez-Giménez, On the connectivity of dynamic random geometric graphs, Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2008), 601-610.

  H. Gebauer, On the Number of Hamilton Cycles in Bounded Degree Graphs, Proc. 5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (2008), 241-248.

  A. Razen, J. Snoeyink, E. Welzl, Number of Crossing-Free Geometric Graphs vs. Triangulations, Electronic Notes in Discrete Mathematics 31 (2008), 195-200, and Proc. of the International Conference on Topological & Geometric Graph Theory (TGGT) (2008), 188-193.

  P. Sankowski, Algebraic Graph Algorithms, Proc. 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science 5162, (2008), 68-82.

  D. Scheder, Guided Search and a Faster Deterministic Algorithm for 3-SAT, Proc. 8th Latin American Theoretical Informatics Symposium (LATIN) (2008), LNCS 4957, 60-71.

  D. Scheder, P. Zumstein, How many conflicts does it need to be unsatisfiable?, Proc. 11th International Conference on Theory and Applications of Satisfiability Testing (SAT) (2008), LNCS 4996, 246-256.

  S. Smorodinsky, M. Sulovský, U. Wagner, On Center Regions and Balls Containing Many Points, Proc. 14th Annual International Computing and Combinatorics Conference (COCOON) (2008), LNCS 5092, 363-373.

  P. Traxler, On the time complexity of constraint satisfaction, Proc. of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC) (2008), 190-201.

• Other (including submitted work)

  A. Razen, A Lower Bound for the Transformation of Compatible Perfect Matchings, Proc. 24th European Workshop on Computational Geometry (EuroCG) (2008), 115-118.

  E. Welzl, Kleinster umschliessender Kreis (Ein Demokratiebeitrag aus der Schweiz?), Taschenbuch der Algorithmen, (B. Vöcking et al., Eds.), Springer-Verlag Berlin Heidelberg, eXamen.press, (2008) 385-388.

Lectures

R. BERKE
"The Linear Arboricity of Odd Regular Graphs with Large Girth", Conference on Relations, Orderings, and Graphs in Computer Science (ROGICS 2008), Mahdia, Tunisia (May 13, 2008).
"Polychromatic Colorings of Plane Graphs", Symposium on Computational Geometry (SoCG 2008), Washington DC, USA (June 11, 2008).

Y. BRISE
"Violator Spaces - An Optimization Framework", Combinatorial Geometry and Optimization Seminar, EPFL, Lausanne (Nov 20, 2008).

T. CHRIST
"Improved Bounds for Wireless Localization", 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), Göteborg, Sweden (Jul 2, 2008).

K. FUKUDA
"Exact algorithms and software in optimization and polyhedral computation", The International Symposium on Symbolic and Algebraic Computation (ISSAC 2008), Hagenberg, Austria (Jul 20-23, 2008, tutorial lecture).

B. GÄRTNER
"Regular Unique Sink Orientations", Internationales Begegnungs- und Forschungszentrum für Informatik, Workshop on Design and Analysis of Randomized and Approximation Algorithms, Schloss Dagstuhl, Germany (May 14, 2008).
"Regular Unique Sink Orientations", Monday Lecture of the Graduiertenkolleg Methods for Discrete Structures, Freie Universität Berlin, Germany (May 19, 2008).
"Regular Unique Sink Orientations", Otto-von-Guericke-Universität Magdeburg, Germany (May 20, 2008).

H. GEBAUER
"On the Number of Hamilton Cycles in Bounded Degree Graphs", 5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2008), San Francisco, USA (Jan 19, 2008).
"On the number of Hamilton Cycles in 3-regular graphs", Discrete Mathematics and Optimization Seminar, McGill University, Montreal, Canada (Dec 1, 2008).

A. RAZEN
"A Lower Bound for the Transformation of Compatible Perfect Matchings", 24th European Workshop on Computational Geometry (EuroCG 2008), Loria Nancy, France (Mar 19, 2008).
"Number of Crossing-Free Geometric Graphs vs. Triangulations", Topological & Geometric Graph Theory (TGGT 2008), Paris, France (May 22, 2008).

P. SANKOWSKI,
"Algebraic Graph Algorithms", 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Torun, Poland (Aug 25, 2008; invited lecture).

M. SULOVSKÝ
"On Center Regions and Balls Containing Many Points", The 14th Annual International Computing and Combinatorics Conference (COCOON 2008), Dalian, China (Jun 29, 2008).

D. SCHEDER
"Guided Search and a Faster Deterministic Algorithm for 3-SAT", 8th Latin American Theoretical Informatics Symposium (LATIN 2008), Buzios, Brazil (April 7, 2008).
"How many conflicts does it need to be unsatisfiable?", 11th International Conference on Theory and Applications of Satisfiability Testing (SAT 2008), Guangzhou, China (May 15, 2008).

T. SZABÓ
"Thresholds for Positional Games", Mathematisches Forschungsinstitut Oberwolfach, Workshop on Combinatorics, Oberwolfach, Germany (Jan 8, 2008).
"Thresholds for biased positional games", Renyi Institute, Combinatorics Seminar, Budapest, Hungary (Feb 21, 2008).
"On the rules of avoiding", Special Session "Extremal and Probablistic Combinatorics", American Mathematical Society / Brazilian Mathematical Society Joint International Meeting, Rio de Janeiro, Brazil (Jun 5, 2008).
"Relaxed Colorings of Graphs", Minisymposium "Graph Coloring", 14th SIAM Meeting on Discrete Mathematics, University of Vermont, Burlington, USA (Jun 18, 2008).

P. TRAXLER
"The Time Complexity of Constraint Satisfaction", 3rd International Workshop on Parameterized and Exact Computation, Victoria, Canada (May, 2008).
"Exponential Time Complexity of Constraint Satisfaction", Internationales Begegnungs- und Forschungszentrum für Informatik, Seminar on Moderately Exponential Time Algorithms, Schloss Dagstuhl, Germany (Oct 23, 2008).

U. WAGNER
"Hardness of Embedding Simplicial Complexes", Theoretical Computer Science Seminar, Hebrew University of Jerusalem, Israel (Jul 16, 2008).
"Hardness of Embedding Simplicial Complexes", Computational Geometry Seminar, Tel-Aviv University, Israel (Jul 23, 2008).
"On the circle containment problem", Prague Midsummer Combinatorial Workshop, Czech Republic (Aug 1, 2008).
"Hardness of Embedding Simplicial Complexes", Workshop of Discrete Geometry, Oberwolfach, Germany (Sep 24, 2008).

E. WELZL
"Crossing Free Configurations on Planar Point Sets", Jahrestagung der Deutschen Mathematikervereinigung (DMV' 08), Erlangen, Germany (Sep 16, 2008; plenary lecture).

P. ZUMSTEIN
"On the Minimum Degree of Ramsey Minimal Graphs", Discrete Mathematics and Optimization Seminar, McGill University, Montreal, Canada (Nov 5, 2008).

Courses and Seminars

Fall 08

See also the Course Catalogue

• Algebraic Methods in Combinatorics, D. Hefetz, U. Wagner; contact assistant: Tobias Christ.
• Algorithms, Probability, and Computing, A. Steger, E. Welzl, P. Widmayer; (VL Mo13-14 CAB G11, Tu14-16 CAB G51; UE We13-15, Th8-10, Fr14-16) contact assistant: Heidi Gebauer.
• Computational Geometry, B. Gärtner, M. Hoffmann; (VL Mo14-16 CAB G59, Th13-14 CAB G59, UE Th14-16 IFWA32.1) contact assistant: Marek Sulovský.
• Diskrete Mathematik (D-ITET), A. Steger, E. Welzl; (VL Mo10-12 CAB G11, UE Fr10-12 biweekly) contact assistants: Torsten Mütze.
• Graphs and Algorithms: Advanced Topics, D. Hefetz, U. Wagner; (VL We10-12 CAB G56, UE Th10-12 CHN D42) contact assistant: Michael Hoffmann.
• Informatik (D-MATH, D-PHYS), B. Gärtner, J. Hromkovic; (VL Tu13-15, UE Tu15-17) contact assistant: Yves Brise.
• Satisfiability of Boolean Formulas - Combinatorics and Algorithms, E. Welzl; (VL Fr10-12 CAB G52, Fr15-16 CAB G52, UE Fr12-13 CAB G52) contact assistant: Robin Moser.
• Theory of Computing (Theoretische Informatik), J. Hromkovic, E. Welzl; (VL Th9-11 HG F7, Fr8-10 HG F5, UE We13-15, discussion hour Th12-13 HG F7) contact assistant: Sebastian Seibert.
• Optimization and Applications Seminar, K. Fukuda, B. Gärtner, P. Kall, D. Klatte, H. Lüthi, M. Morari; (K Mo16-18 HG E41).
• Optimization Techniques, H. Lüthi, K. Fukuda; (VL Tu10-12, UE Mo13-15).
• Reading Seminar, U. Wagner, E. Welzl; (SE Fr15-17 CAB G52).
• Seminar der Theoretischen Informatik (Mittagsseminar), B. Gärtner, D.Hefetz, M. Hoffmann, A. Steger, U. Wagner, E. Welzl; (SE Tu12-13, Th12-13).
• Seminar zu Approximate Methods in Geometry, B. Gärtner, U.Wagner, E. Welzl; (SE Fr14-16 CAB G59).

Spring 08

See also the Course Catalogue

• Approximate Methods in Geometry, B. Gärtner, U. Wagner, E. Welzl; (VL Tu9-11 CAB H52, UE Tu11-12 CAB H52); contact assistant: Marek Sulovský.
• Optimization and Applications Seminar, K. Fukuda, B. Gärtner, P. Kall, D. Klatte, H. Lüthi, M. Morari; (K Mo16-18 HG E41).
• Topological Methods in Combinatorics and Geometry (English), J. Matoušek, U. Wagner; (VL Th10-12 CAB H52, UE Th13-14 CAB G57).
• Reading Seminar, T. Szabó, U. Wagner, E. Welzl; (SE Fr15-17 CAB G52).
• Seminar SAT, E. Welzl; (SE Tu13-15 CAB G52).
• Seminar der Theoretischen Informatik (Mittagsseminar), B. Gärtner, M. Hoffmann, A. Steger, T. Szabó, U. Wagner, E. Welzl; (SE Tu12-13 CAB G51, Th12-13 CAB G51).
• Seminar zur Algorithmischen Geometrie, B. Gärtner, M. Hoffmann, E. Welzl; (SE Fr14-16 CAB G59).
• Summer School: New Algorithmic Paradigms in Optimization, K. Fukuda, H.-J. Lüthi, E. Welzl; (Jun 16 - Jul 1, Zürich and Monte Verita).

Organization of Workshops etc.

• Sparse Quasirandom Graphs: Constructions and Applications, two-week minicourse within the MDS Doc-Course "Random and Quasirandom Graphs", Humboldt University, Berlin, Germany, May 19-30, 2008, (T. Szabó)
• Summer School: New Algorithmic Paradigms in Optimization, Zürich and Monte Verita, Jun 16 - Jul 1, 2008, (K. Fukuda, H.-J. Lüthi, E. Welzl)
• 6th Gremo Workshop on Open Problems 2008, Trogen (AR), Switzerland, Sep 8 - 10, 2008, (Michael Hoffmann)
• Workshop on Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach, Germany, Sep 21 - 27, 2008, (Martin Henk, Jiří Matoušek, Emo Welzl)

Dissertations

• Robert Berke, Colorings and Transversals of Graphs
  Advisors: Tibor Szabó (co-referee), Emo Welzl (referee) / Co-referee: Nati Linial, Hebrew University of Jerusalem, Israel. / Defense: May 19, 2008

Master and Diploma Theses

• Daniel Donatsch, Variants of the smallest enclosing ball problem
  Advisor: B. Gärtner / 8.2.2008
• Gabriel Katz, Arrangements of Tropical Halfspaces
  Advisors: M. Jaggi, U. Wagner / 5.9.2008
• Lucia Keller, Probabilistic and combinatorial methods of partial satisfaction of k-satisfiable CNF formulas
  Advisor: D. Scheder / 7.2.2008
• Rafael Robleda, A Sparse Version of CGAL's Quadratic Programming Solver
  Advisor: B. Gärtner / 5.2.2008

Bachelor and Semester Theses / Internship Projects

• Ruedi Becker, Bounded Two-Colorings of Planar Subcubic Graphs
  Advisor: R. Berke / 3.7.2008
• Dan Bühler, Regular Unique Sink Orientations
  Advisor: B.Gärtner / 5.8.2008
• Andrea Francke, Bounded Degree Spanning Trees
  Advisor: Michael Hoffmann / 31.10.2008
• Sarah Hauser, Proper Colorings of Hypergraphs
  Advisors: R. Berke, P. Zumstein / 1.2.2008
• Praveen Kumar Naga Katta, Polychromatic colorings of the cube,
  Advisor: Tibor Szabó / 15.7.2008
• Dave Meyer, Unique Sink Orientations in Gittergraphen
  Advisor: B. Gärtner / 30.12.2008
• Thao Minh Vuong, Triple-Crossings of Triangles and Equivariant Methods,
  Advisor: Uli Wagner / 15.7.2008
• Lutz Warnke, Symmetry in Satisfiability (Excellence Project)
  Advisor: E. Welzl / 26.8.2008

Miscellaneous

R. BERKE
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Coordinator. (until Sep 12)
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

Y. BRISE
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 08).
Webmaster www-gremo.
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

T. CHRIST
Teach. Assistance Algebraic Methods in Combinatorics (Fall 08).
Attended the conferences/courses/workshops:
MDS (Pre)Doc-Course 2008 - Random and Quasirandom Graphs, HU Berlin, Germany (May 5 - 9, 2008).
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

K. FUKUDA
Editorial Board Member of European J. Combinatorics, Computational Geometry: Theory and Applications, Applied Mathematics Research eXpress.
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

B. GÄRTNER
Coordinator ACS.
Member of the CGAL Editorial Board.
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

H. GEBAUER
Teach. Assistance Algorithms, Probability, and Computing (Fall 08).
Teach. Assistance Coordinator. (from Sep 13)
Attended the conferences/courses/workshops:
MDS (Pre)Doc-Course 2008 - Random and Quasirandom Graphs, HU Berlin, Germany (May 19 - 30, 2008).
5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 08), San Francisco, USA (Jan 19).
19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 08), San Francisco, USA (Jan 20 - 22).

M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
Program committee member of 16th Annual European Symposium on Algorithms (ESA 08), Engineering and Applications Track, Karlsruhe, Germany, (Sep 15-19, 2008).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

M. JAGGI
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

R. MOSER
Teach. Assistance Satisfiability of Boolean Formulas (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

A. RAZEN
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Theoretische Informatik (Fall 08).
Coordinator Mittagsseminar.
Attended the conferences/courses/workshops:
24th European Workshop on Computational Geometry (EuroCG 08), Loria Nancy, France (Mar 18 - 20, 2008).
MDS (Pre)Doc-Course 2008 - Random and Quasirandom Graphs, HU Berlin, Germany (May 5 - 9, 2008).
Topological & Geometric Graph Theory (TGGT 2008), Paris, France (May 19-23, 2008).
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

P. SANKOWSKI
Program committee member of ICALP 2009.

D. SCHEDER
Teach. Assistance Einsatz von Informatikmitteln (D-BIOL, D-CHAB) (Spring 08).
Teach. Assistance Algorithms, Probability, and Computing (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).
Building Bridges - A conference on mathematics and computer science in honour of László Lovász, Budapest, Hungary (Aug 5 - 9, 2008).
Fete of Combinatorics and Computer Science, An international conference on combinatorics and computer science, Keszthely, Lake Balaton, Hungary (Aug 11 - 15, 2008).

M. SULOVSKÝ
Teach. Assistance Approximate Methods in Geometry (Spring 08).
Teach. Assistance Computational Geometry (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).
The 14th Annual International Computing and Combinatorics Conference (COCOON 2008), Dalian, China (Jun 27 - 29, 2008).
Building Bridges - A conference on mathematics and computer science in honour of László Lovász, Budapest, Hungary (Aug 5 - 9, 2008).
Fete of Combinatorics and Computer Science, An international conference on combinatorics and computer science, Keszthely, Lake Balaton, Hungary (Aug 11 - 15, 2008).

P. TRAXLER
Teach. Assistance Anwendungsnahes Programmieren (Spring 08).
Teach. Assistance Informatik I (D-BAUG) (Fall 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).

E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zürich.

Program committee member of

• 24th Annual Symposium on Computational Geometry (SoCG 2008), Washington, USA (Jun 9 - 11, 2008)

Editorial Board member of

• ACM Transacations on Computation Theory, (Lance Fortnow, Ed.), ACM
• Mathematik Kompakt, (M. Brokate, H.W. Engl, K.-H. Hoffmann, G. Kersting, G. Stroth, E. Welzl, Eds.), Birkhäuser Verlag
• Discrete and Computational Geometry, (J. Goodman & R. Pollack, Eds.), Springer Verlag
• Computational Geometry - Theory and Applications, (K. Mehlhorn & J.-R. Sack, Eds.), Elsevier Science Publishers
• Journal for Universal Computer Science, (H. Maurer, Ed.), Springer Verlag (electronic journal)
• Fundamenta Informaticae, (Annales Societatis Mathmaticae Polonae, A. Skowron, Ed.), IOS Press
• ORDER, (Dwight Duffus, Ed.), Kluwer Academic Press (until Sep 16, 2008)

Member (chair, contact person) of selection committees for

• Professor / Assistant Professor (Tenure Track) of Food Material Science, Department of Agricultural and Food Sciences (chair)
• Professorships in Mathematics, Department of Mathematics
• Professorship in Biological Engineering, Department of Chemistry and Applied Biosciences (chair)
• Assistant Professor (Tenure Track) of Management of Information Systems (chair)
• Faculty positions in computer science at the School of Computer and Communication Sciences, EPF Lausanne

Coreferee for dissertations of

• Stefan Funke, Scientific Works in Computational Geometry (Computer Science, Universität des Saarlandes, Germany)

Member of the EATCS Council (European Association for Theoretical Computer Science).
Member of the EATCS Award committee (with Catuscia Palamidessi, chair, and Pavlos Spirakis).
Member of the European Symposium on Algorithms (ESA)-steering committee.
Member of the peer evaluation committee of the Computer Science Department of the University of Vienna.

Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
Mitglied der Studienkommission der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.

P. ZUMSTEIN
Teach. Assistance Datenstrukturen und Algorithmen (D-INFK) (Spring 08).
Attended the conferences/courses/workshops:
New Algorithmic Paradigms in Optimization (NAPIO 2008), Zürich and Monte Verita, Switzerland (Jun 16 - Jul 1, 2008).
Building Bridges - A conference on mathematics and computer science in honour of László Lovász, Budapest, Hungary (Aug 5 - 9, 2008).