Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd GÃ¤rtner
Institut für Theoretische Informatik | ||
Departement Informatik | ||
ETH Zürich | phone | +41-44-632 73 92 |
CH-8092 Zürich | fax | +41-44-632 10 63 |
Quick Links: | Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Bachelor Theses, Miscellaneous |
(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
(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
(Financed by the Swiss National Science Foundation.)
Proper coloring of graphs and the chromatic number (the smallest
number of colors which allow a proper coloring) are among the most important concepts
of graph theory. Numerous problems of pure mathematics and theoretical computer science
require the study of proper colorings and even more real-life problems require the calculation
or at least an estimation of the chromatic number. Nevertheless, there is the discouraging
fact that the calculation of the chromatic number of a graph or the task of finding an
optimal proper coloring are both famous intractable problems, even fast approximation is
probably not possible. This is one of our motivations to study relaxations of proper coloring,
because in some theoretical or practical situations a small deviation from proper is still
acceptable, while the problem could become tractable. Another reason for the introduction of
relaxed colorings is that in certain problems the use of the full strength of proper coloring
is an ``overkill''. Often a weaker concept suffices and provides better overall results.
In the project we study a relaxation of proper coloring, which allows
the presence of some small level of conflicts in the color assignment.
Our approach relies heavily on the theory of transversals.
A set of vertices in a partitioned graph is called a transversal if
it contains exactly one vertex from each class. Transversals with
special properties surface in many different problems of combinatorics
and theoretical computer science, when an appropriate auxiliary graph is
constructed and a transversal of a certain kind is sought after. In particular independent
transversals saw numerous applications in the study of list chromatic number,
the satisfiability of boolean formulas, the linear arboricity of graphs and
relaxed colorings of graphs. The quest for transversal results also inspired a great
methodological advance in the field of combinatorics, as beautiful proofs
applying combinatorial topology appeared.
Contact: T. Szabó
(Funded by the Swiss National Science Foundation.) The medial
axis is one of the fundamental geometric concepts in computational
geometry, 3D shape modeling, and image processing. Introduced by Blum
as a tool for image analysis, the medial axis has since then been used
in many different contexts, e.g., shape recognition, motion planing
and reverse engineering.
Our interest in the medial axis is twofold. First, the medial axis is
a very interesting mathematical object in itself that poses many
computational and mathematical challenges. Second, the medial axis
conceptually appears in many geometric modeling applications. In most
of these applications a shape is given to us only in form of a finite
sample, e.g., a laser range scan of a 3D solid, or a set of positions
of the atoms of a molecule measured by x-ray crystallography. The use
of the medial axis for such data has been mostly restricted to
theoretical analysis. Few applications have been presented that
explicitly compute the medial axis for geometric processing tasks on
acquired sample sets. One of the main reasons for its limited
practical use is the notorious instability of the medial axis
transform.
Our goal is to give a new definition of an approximate medial axis
that is stable under a set of meaningful perturbations and at the same
time respects the intrinsic scales of the data. This would allow
scalable geometric processing operations based on the medial axis for
non-uniformly sampled data, thus greatly enhancing the set of
potential input data. Additionally, we want to derive algorithms for
maintaining the medial axis for kinetic data sets, i.e., shapes that
move or deform over time. Motion is fundamental in many disciplines
that model the physical world, such as robotics, computer graphics,
computational biology, or physics. A kinetic medial axis is of great
interest in such fields, as it is directly linked to the concept of an
interface between two or more different shapes. An interface can be
defined as the subset of the medial axis of the dual shape that
contains all points with nearest neighbors in more than one
shape. Interfaces play an important role in machine learning as
decision boundaries, in fluid dynamics simulations as boundary between
different fluids, and in molecular dynamics simulations as
inter-molecular or contact surfaces between different macromolecules.
Contact: J. Giesen, M. Pauly (Institute of Computational Sciences)
(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ó
(Funded by INRIA.) Understanding the way proteins adopt their 3D structure, the folding problem, or the way macro-molecular complexes get formed, the docking problem, are two of the most challenging problems in structural biology. Since proteins in vivo vibrate at various frequencies addressing the aforementioned problems requires modeling protein flexibility. In this project we plan on developing new approaches towards modeling protein flexibility based on geometric and topological tools.
Contact: F. Cazals (INRIA Sophia Antipolis, project leader), M. Nilges (Institut Pasteur), J. Giesen
(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
(Financed by the
Eidgenössische Materialprüfungs- und Forschungsanstalt, EMPA.)
The set of colors that can be represented or reproduced by some device
or process is called a gamut. In general different devices
have different gamuts. Hence, when processing images from some
input device to some output device one often faces the problem that
the gamut changes, often the size of the gamut of the output device is the
bottleneck in the transition and information gets lost. The challenge is
to define and compute good (tailored) gamut mappings.
The problem of defining and computing gamut mappings is amenable to
methods from low dimensional computational geometry, because in color
spaces like CIELAB a gamut is represented as a three-dimensional polytope.
The purpose of this project is to develop fast and robust methods for
computing gamuts and gamut mappings.
(Financed by the Swiss National Science Foundation.)
Estimating product preferences of individuals by means
of questionnaires is daily practice in market research. Under the name of
conjoint analysis a whole family of methods has been developed
and used to estimate the preferences of individuals. Conjoint analysis
started in 1964 with the seminal paper by Luce and Tukey and was introduced
to the marketing literature by Green and Rao in 1971. Since then conjoint
analysis has received much attention from practitioners in market research
as well as from researchers in academia. Its importance can be stressed by
its many applications, e.g. in new product planning, product
improvement, pricing, advertising, distribution and market segmentation
and simulation.
In this project we study a variant of conjoint analysis which is called
choice based conjoint analysis (CBC). In CBC product preferences
of an individual are learned from a sequence of pairwise product comparisons.
In each comparison the respondent only has to state which out of the two
products she prefers. The comparisons are used to estimate parameters in
a utility function that is defined over the product space. We focus on two
questions. First, how many comparisons have to be performed by the respondent
at least in order to get optimal knowledge on the parameters. Second, we
want to find a strategy to present product pairs to the respondent such
that one gets optimal knowledge on the parameters by presenting only the
minimum number of product pairs necessary. That is, we want to determine
the intrinsic complexity of CBC. The first problem asks for a lower bound
on this complexity whereas the second problem asks for an upper bound.
Contact: J. Giesen
(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).
Contact: E. Feichtner, ETHZ, K. Fukuda, ETHZ and EPFL, P. Parrilo, ETHZ, and R. Thomas, University of Washington
B. Gärtner, R. Veltkamp (Eds.), Special Issue on CGAL (the Computational Geometry Algorithms Library), Computational Geometry - Theory and Applications 38:1-2 (2007) 1-128.
N. Alon, A. Krech, T. Szabó, Turán's Theorem in the hypercube, SIAM Journal on Discrete Mathematics 21 (2007) 66-72.
T. Asano, J. Matoušek, T. Tokuyama, The distance trisector curve, Advances in Mathematics 212 (2007) 338-360.
T. Asano, J. Matoušek, T. Tokuyama, Zone diagrams, SIAM Journal of Computing 37:4 (2007) 1182-1198.
R. Berke, T. Szabó, Relaxed two-coloring of cubic graphs, Journal of Combinatorial Theory (Series B) 97:4 (2007) 652-668.
F. Cazals, J. Giesen, M. Pauly, A. Zomorodian, The conformal alpha shape filtration, The Visual Computer 22 (2006) 531-540.
T.K. Dey, J. Giesen, S. Goswami, Delaunay triangulation approximates anchor hull, Computational Geometry - Theory and Applications 36 (2007) 131-143.
K. Fukuda, A. Jensen, N. Lauritzen and R. Thomas, The generic Gröbner walk, Journal of Symbolic Computation 42 (2007) 298-312.
K. Fukuda, A. Jensen and R. Thomas, Computing Gröbner fans, Mathematics of Computation 76 (2007) 2189-2212.
K. Fukuda and T. Uno, Polynomial time algorithms for maximizing the intersection volume of polytopes, Pacific Journal on Optimization 3 (2007) 37-52.
K. Fukuda and C. Weibel, f-vectors of Minkowski additions of convex polytopes, Discrete Computational Geometry 37 (2007) 503-516.
B. Gärtner, V. Kaibel, Two new bounds for the Random-Edge simplex algorithm, SIAM Journal on Discrete Mathematics 21 (2007) 178-190.
J. Giesen, M. John, The flow complex: a data structure for geometric modeling, Computational Geometry - Theory and Applications 39 (2008) 178-190.
J. Giesen, K. Mueller, E. Schuberth, L. Wang and P. Zolliker, Conjoint Analysis for Measuring the Perceived Quality in Volume Rendering, IEEE Transactions on Visualization and Computer Graphics 13:6 (2007) 1664-1671.
J. Giesen, E. Schuberth, K. Simon, P. Zolliker, O. Zweifel, Image-Dependent Gamut Mapping as Optimization Problem, IEEE Transactions on Image Processing 16 (2007) 2401-2410.
D. Hefetz, M. Krivelevich, T. Szabó, Avoider-Enforcer games, Journal of Combinatorial Theory (Series A) 114 (2007) 840-853.
D. Hefetz, M. Krivelevich, T. Szabó, Bart-Moe games, JumbleG and discrepancy, European Journal of Combinatorics 28 (2007) 1131-1143.
S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel, An adaptable and extensible geometry kernel, Computational Geometry - Theory and Applications 38:1-2 (2007) 16-36.
T. Asano, J. Matoušek, T. Tokuyama: Zone diagrams, Proc. 18th ACM-SIAM Symposum on Discrete Algorithms (SODA), (2007) 756-765.
O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Pór, F. Santos, B. Speckmann, B. Vogtenhuber, Maximizing maximal angles for plane straight line graphs, Proc. 10th Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 4619 (2007) 458-469.
Marc Benkert, Martin Nöllenburg, Takeaki Uno, Alexander Wolff, Minimizing intra-edge crossings in wiring diagrams and public transport maps, Proc. 14th Int. Symposium on Graph Drawing (GD), Lecture Notes in Computer Science 4372 (2007) 270-281.
S. Gandhi, S. Suri, E. Welzl, Catching elephants with mice: sparse sampling for monitoring sensor networks, Proc. 5th International ACM Conference on Embedded Networked Sensor Systems (SenSys), (2007) 261-274.
J. Giesen, D. Mitsche, E. Schuberth, A spectral approach to collaborative ranking, Proc. AAAI 07 Workshop on Preference Handling for Artificial Intelligence, (2007) 47-52.
J. Giesen, D. Mitsche, E. Schuberth, Collaborative ranking: an aggregation algorithm for individuals' preference estimation, Proc. 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM), Lecture Notes in Computer Science 4508 (2007) 58-67.
C. Käppeli, D. Scheder, Partial Satisfaction of k-Satisfiable Formulas, Proc. European Conference on Combinatorics (EuroComb), (2007) 497-501.
V. Pauli, L. Lampe, R. Schober and K. Fukuda, Multiple-symbol differential detection based on combinatorial geometry, Proc. IEEE International Conference on Communications (ICC 2007), (2007) 827-832.
D. Scheder, P. Zumstein, Satisfiability with exponential families, Proc. 10th International Conference on Theory and Applications of Satisfiability Testing (SAT), Lecture Notes in Computer Science 4501 (2007) 148-158.
O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, F. Santos, B. Speckmann, B. Vogtenhuber, Maximizing maximal angles for plane straight line graphs, Proc. 23rd European Workshop on Computational Geometry (EuroCG) (2007) 98-101.
V. Anuradha, C. Jain, J. Snoeyink, T Szabó, How long can a graph be kept planar?, 17th Fall Workshop on Computational and Combinatorial Geometry (2007).
N. Benbernou, E. D. Demaine, M. L. Demaine, M. Hoffmann, M. Ishaque, D. L. Souvaine, Cs. D. Tóth, Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs, Proc. 19th Canadian Conference on Computational Geometry (CCCG) (2007) 13-16.
K. Buchin, A. Razen, T. Uno, U. Wagner, Transforming spanning trees: a lower bound, Proc. 23rd European Workshop on Computational Geometry (EuroCG) (2007) 166-169.
F. Cazals, J. Giesen, Delaunay triangulation based surface reconstruction, Effective Computational Geometry of Curves and Surfaces, (J.D. Boissonnat, M. Teillaud, Eds.) Springer-Verlag (2007), 231-276.
J. Giesen, E. Schuberth, The combinatorial structure of polyhedral choice based conjoint analysis; Conjoint Measurement: Methods and Applications, Editors A. Gustafsson, A. Herrmann and F. Huber, Springer-Verlag (2007) 258-271.
R. BERKE
"The Morphism Chromatic Number",
21st British Combinatorics Conference (BCC 07),
University of Reading, UK (Jul 10, 2007).
"Transversals in Multipartite Graphs",
Oxford Combinatorics Seminar,
Oxford, UK (Jul 17, 2007).
"Deciding relaxed two-colorability",
Theory Seminar, CS Departement, SFU, Vancouver, BC, Canada (Sep 19, 2007).
B. GÄRTNER
"Solving Linear and Quadratic Programs in CGAL",
ACS General Workshop,
FU Berlin, Germany
(May 11, 2007).
"Approximate smallest enclosing ellipsoids in CGAL",
ACS Workshop on Robust Shape Operations,
INRIA, Sophia Antipolis, France
(Sep 28, 2007).
M. HOFFMANN
"Maximizing Maximal Angles in Planar Straight Line Graphs",
Complexity Theory and Algorithmics Seminar, University of Liverpool,
UK (Nov 8, 2007).
A. RAZEN
"Transforming Spanning Trees: A Lower Bound",
23rd European Workshop on Computational Geometry (EuroCG 07),
TU Graz, Austria
(Mar 20, 2007).
D. SCHEDER
"Partial Satisfaction of k-Satisfiable Formulas",
European Conference on Combinatorics,
Graph Theory and Applications (EuroComb 07)
,
Seville University, Sevilla, Spain
(Sep 14, 2007).
T. SZABÓ
"On a Hamiltonicity Criterion and Positional Games",
Workshop on Quasi-random structures, regularity lemmas and their applications,
Renyi Institute, Budapest, Hungary
(Jan 25, 2007).
"Relaxed Coloring of Cubic Graphs -- a Hardness Jump",
Combinatorics Seminar,
Renyi Institute, Budapest, Hungary
(Feb 22, 2007).
"Maker-Breaker Games on the Complete Graph",
Miniworkshop on Positional Games,
Mathematisches Forschungsinstitut Oberwolfach,
Germany
(Apr 9, 2007).
"Avoider-Enforcer Games on the Complete Graph",
Miniworkshop on Positional Games,
Mathematisches Forschungsinstitut Oberwolfach,
Germany
(Apr 10, 2007).
"Random graph intuition and pseudorandomness in positional games",
Mathematics Colloquium, EPFL, Lausanne, Switzerland
(May 10, 2007).
"Pseudorandomness in positional games",
13th International Conference on Random Structures and Algorithms,
Tel Aviv University, Tel Aviv, Israel
(May 31, 2007).
"On the randomized simplex algorithm in abstract cubes",
Optimization and Applications Seminar,
ETH Zurich and University of Zurich,
Switzerland
(Nov 19, 2007).
"Random graph intuition and pseudorandomness in positional games",
Monday Lecture of the Research Training
Group "Methods for Discrete Structures",
Freie Universität Berlin, Berlin, Germany
(Dec 3, 2007).
U. WAGNER
"h-Matrices of Levels in Arrangements",
Cornell Discrete Geometry and Combinatorics Seminar,
Cornell University, Ithaca, USA
(Nov 26, 2007).
E. WELZL
"Counting Crossing-Free Configurations on Planar Point Sets",
European Conference on
Combinatorics, Graph Theory and Applications (EuroComb 07),
Seville University, Sevilla, Spain
(Sep 12, 2007; invited talk).
"Counting of Crossing-Free Geometric Graphs",
Significant Advances in Computer Science (SACS 07),
Graz University of Technology, Graz, Austria,
(Nov 6, 2007).
P. ZUMSTEIN
"Satisfiability with Exponential Families",
Tenth International Conference on
Theory and Applications of Satisfiability Testing (SAT 07),
Lisbon, Portugal
(May 29, 2007).
R. BERKE
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Diskrete Mathematik (SS07).
Teach. Assistance Informatik II (D-BAUG) (SS07).
Teach. Assistance Coordinator.
Attended the conferences/courses/workshops:
21st British Combinatorics Conference (BCC 07),
Reading University, UK, (Jul 9-13, 2007).
Combinatorial Potlatch, University of Victoria, BC, Canada, (Sep 29, 2007).
Y. BRISE
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Geometric Computations in Molecular Biology (SS07).
Teach. Assistance Informatik (D-MATH, D-PHYS) (Fall 07).
Webmaster www-gremo (since June).
T. CHRIST
Teach. Assistance Diskrete Mathematik (D-ITET) (WS06/07).
Teach. Assistance Diskrete Mathematik (SS07).
Teach. Assistance Theory of Computing (Fall 07)
Attended the conferences/courses/workshops:
The Victor Rothschild Memorial Symposium, 11th Midrasha Mathematicae,
Polytopes Graphs and Convexity, Hebrew University of Jerusalem, Israel (May 6-11, 2007).
K. FUKUDA
Member of
Organization committee for 5th Joint IBM-Swiss OR Days
Editorial Board Member of
European J. Combinatorics, Computational Geometry: Theory and Applications,
Applied Mathematics Research eXpress.
B. GÄRTNER
Coordinator ACS.
Member of the CGAL Editorial Board.
H. GEBAUER
Teach. Assistance Algorithms, Probability, and Computing (Fall 07).
M. HOFFMANN
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Graphs & Algorithms: Advanced Topics (Fall 07).
Informatik Koordinator.
Member of the CGAL Editorial Board.
M. JAGGI
Teach. Assistance Diskrete Mathematik (D-ITET) (Fall 07).
D. MITSCHE
Teach. Assistance Theory of Computing (WS06/07).
A. RAZEN
Teach. Assistance Graph Theory (WS06/07).
Teach. Assistance Discrete Geometry (SS07).
Teach. Assistance Diskrete Mathematik (Fall 07).
Coordinator Mittagsseminar.
Attended the conferences/courses/workshops:
23rd European Workshop on Computational Geometry (EuroCG 07), TU Graz,
Austria, (Mar 19 - 21, 2007).
The Victor Rothschild Memorial Symposium, 11th Midrasha Mathematicae,
Polytopes Graphs and Convexity, Hebrew University of Jerusalem, Israel (May 6-11, 2007).
L. RÜST
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS06/07).
Teach. Assistance Diskrete Mathematik (SS07).
Webmaster www-gremo (until June).
D. SCHEDER
Teach. Assistance Erfüllbarkeit logischer Formeln (SAT) - Kombinatorik und Algorithmen (WS06/07).
Teach. Assistance Datenstrukturen & Algorithmen (SS07).
Teach. Assistance Seminar SAT (SS07).
E. SCHUBERTH
Teach. Assistance Algorithmische Geometrie (WS06/07).
Head of Frauenförderung.
M. SULOVSKÝ
Teach. Assistance Theoretische Informatik (WS06/07).
Teach. Assistance Approximate Methods in Geometry (SS07).
Teach. Assistance Algorithmische Geometrie (Fall 07).
Attended the conferences/courses/workshops:
The Victor Rothschild Memorial Symposium, 11th Midrasha Mathematicae,
Polytopes Graphs and Convexity, Hebrew University of Jerusalem, Israel (May 6-11, 2007).
P. TRAXLER
Teach. Assistance Algorithms, Probability, and Computing (WS06/07).
Teach. Assistance Datenstrukturen & Algorithmen (SS07).
Teach. Assistance Algorithms, Probability, and Computing (Fall 07).
E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.
Program committee member of
Program committee chair of
Editorial Board member of
Member (chair, contact person) of selection committees for
Member of the EATCS Council (European
Association for Theoretical Computer Science).
Member of the EATCS Award committee (with Catuscia Palamidessi and David Peleg, chair).
Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Algorithmik grosser und komplexer Netzwerke" der Deutschen Forschungsgemeinschaft (DFG).
Mitglied der Studienkommission der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.
Election to the Berlin-Brandenburg Academy of Sciences (Mathematisch-Naturwissenschaftliche Klasse).
P. ZUMSTEIN
Teach. Assistance Algorithms, Probability, and Computing (WS06/07).
Teach. Assistance Extremal Combinatorics (SS07).
Teach. Assistance Diskrete Mathematik (D-ITET) (Fall 07).