Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
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, Semester Theses, Miscellaneous |
(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ó
(Financed by the Swiss National Science Foundation.) The main topic of this research is developing new algorithms for enumerating combinatorial objects, such as graphs and polytopes. These objects have some difficulty from the aspects of computational complexity, for example no polynomial time algorithm for checking the isomorphism of two graphs is known. However, these enumeration problems have many applications in optimizations, clustering, data mining, and machine learning, thus we need developments of efficient algorithms, in the sense of both theory and practice.
(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
(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ó
(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 Swiss National Science Foundation.)
Manifold learning is the problem of computing a model of a k-dimensional manifold
embedded non-linearly in d-dimensional Euclidean space only from a finite set of
sample points. Typically k is very small compared to d. The importance of
the problem can be stressed by its many applications, e.g. in speech recognition, weather
forecasting and economic prediction.
Special cases of the manifold learning problem in low dimensions received a lot of
attention in recent years. Most prominent is the surface reconstruction problem where
a two-dimensional manifold embedded in three-dimensional space has to be learned.
Some of the proposed algorithms for surface reconstruction come with the guarantee
that the computed model is a manifold homeomorphic and geometrically close to the
unknown manifold provided some sampling condition is fulfilled. Almost all known
provable algorithms for surface reconstruction use the Delaunay triangulation of the
sample points as basic data structure. Unfortunately the time to compute the Delaunay
triangulation is prohibitive in higher dimensions.
In this project we plan to investigate provable methods for manifold learning in
high dimensions. Starting point should be a sampling condition similar to the
one used in the proofs for surface reconstruction. The most important task in
extending theoretical guarantees known from surface reconstruction to higher
dimensions is to replace the Delaunay triangulation with other proximity data structures.
Contact: J. Giesen
(Financed by the Swiss National Science Foundation.)
Linear programming, as well as several other geometric optimization problems
do have polynomial-time algorithms in the bit model, i.e. when the input size
is measured by the bit complexity of the actual numbers in the data. It
is not known, however, whether there are strongly polynomial algorithms,
whose performance is quantified in terms of arithmetic operations on
input numbers, independently from their bit complexity.
The goal of the project is to find, study, and algorithmically
exploit combinatorial models for certain discrete geometric optimization
problems. Our main motivation is to enhance our understanding of
the combinatorics behind linear programming and related - mostly
geometric - optimization problems, improve on the performance
guarantees of existing algorithms, and possibly discover novel,
more efficient approaches. Classical such models are matroids,
oriented matroids and submodular functions.
Within the last ten years, the concept of LP-type problems has
become a recognized combinatorial model for linear programming and many
other important geometric optimization problems. For many
problems in the class, the currently best (or even optimal) combinatorial
algorithm is an algorithm for general LP-type problems.
In the last couple of years new exciting
combinatorial models for geometric optimization problems
have emerged, such as unique-sink orientations of cubes and
strong LP-type problems. Just like LP-type problems ten years
ago, these new combinatorial abstractions had immediate consequences;
they provide the only available algorithms for certain linear complementarity
problems with nontrivial running time guarantees.
Within this new project, we plan to explore unique-sink orientations,
strong LP-type problems, their relations to each other and
to other known combinatorial models, as well as algorithms for problems fitting
into the respective models.
Contact: B. Gärtner, T. Szabó
(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, R. Thomas, University of Washington
B. Gärtner, J. Matoušek, Understanding and Using Linear Programming, Universitext, Springer (2006).
U. Adamy, M. Hoffmann, J. Solymosi, M. Stojakovic, Coloring octrees, Theoretical Computer Science 363:1 (2006) 11-17.
J. Bang-Jensen, B. Reed, M. Schacht, R. Samal, B. Toft, U. Wagner, On six problems posed by Jarik Nesetril, In: Topics in Discrete Mathematics (M. Klazar, J. Kratochvil, M. Loebl, J. Matoušek, R. Thomas, eds.), Algorithms and Combinatorics 26 (2006) 613-627.
J. Barat, J. Matoušek, D. Wood, Bounded-degree graphs have arbitrarily large geometric thickness, The Electronic Journal of Combinatorics 13:1 (2006).
K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, Sh. Smorodinsky, U. Wagner, E. Welzl, Online conflict-free coloring for intervals, SIAM Journal of Computing 36 (2006) 956-973.
V.G. Deineko, M. Hoffmann, Y. Okamoto, G.J. Woeginger, The traveling salesman problem with few inner points, Operations Research Letters 34:1 (2006) 106-110.
R. Haas and M. Hoffmann, Chordless paths through three vertices, Theoretical Computer Science 351:3 (2006) 360-371.
P. Haxell, T. Szabó, Odd independent transversals are odd, Combinatorics, Probability and Computing 15:1-2 (2006) 193-211.
J. Matoušek, The number of unique-sink orientations of the hypercube, Combinatorica 26 (2006) 91-99.
J. Matoušek, M. Sharir, S. Smorodinsky, U. Wagner, k-sets in four dimensions, Discrete Computational Geometry 35:2 (2006) 177-191.
J. Matoušek, T. Szabó, RANDOMEDGE can be exponential in abstract cubes, Advances in Mathematics 204 (2006) 262-277.
M. Sharir, E. Welzl, On the number of crossing-free matchings, cycles, and partitions, SIAM Journal of Computing 36 (2006) 1342-1359.
T. Szabó, G. Tardos, Extremal problems for transversals in graphs with bounded degree, Combinatorica 26:3 (2006) 333-351.
T. Asano, J. Matoušek, T. Tokuyama, The distance trisector curve, Proc. 38th ACM Symposium on Theory of Computing (STOC) (2006) 336-343.
R. Berke, T. Szabó, Deciding relaxed two-colorability - a hardness jump, Proc. 14th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 4168 (2006) 124-135.
B. Gärtner, J. Matoušek, L. Rüst, P. Škovroň, Violator spaces: structure and algorithms, Proc. 14th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 4168 (2006) 387-398.
B. Gärtner, I. Schurr, Linear Programming and unique sink orientations, Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006) 749-757.
J. Giesen, E. Ramos, B. Sadri, Medial axis approximation and unstable manifolds, Proc. 22nd Annual ACM Symposium on Computational Geometry (SoCG) (2006) 327-336.
J. Giesen, E. Schuberth, K. Simon, D. Zeiter, P. Zolliker, A framework for image-dependent gamut mapping, Proc. IS&T/SPIE Symposium on Electronic Imaging (2006) 605805-1-11.
J. Giesen, E. Schuberth, M. Stojakovic, Approximate sorting, Proc. 7th Latin American Theoretical Informatics Symposium (LATIN), Lecture Notes in Computer Science 3887 (2006) 524-531.
M. Kiyomi, S. Kijima, T. Uno, Listing chordal graphs and interval graphs, Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (2006) 68-77.
N. Mitra, L. Guibas, J. Giesen, M. Pauly; Probabilistic fingerprints for shapes, Proc. 4th Symposium on Geometry Processing (SGP) (2006) 121-130.
M. Sharir, E. Welzl, On the number of crossing-free matchings, (cycles, and partitions), Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006) 860-869.
M. Sharir, E. Welzl, Random triangulations of planar point sets, Proc. 22nd Annual ACM Symposium on Computational Geometry (SOCG) (2006) 273-281.
U. Wagner, On a generalization of the Upper Bound Theorem, Proc. 47th Annual Symposium on the Foundations of Computer Science (FOCS) (2006) 635-645.
K. Fukuda, T. Uno, Algorithms for maximizing the volume of intersection of polytopes, Proc. 22nd European Workshop on Computational Geometry (EuroCG) (2006).
J. Giesen, E. Schuberth, K. Simon, P. Zolliker, A kernel approach to gamut boundary computation, Proceedings of the 14th European Signal Processing Conference (EUSIPCO) (2006) (invited paper).
M. Hoffmann, Cs. D. Tóth, Spanning trees across axis-parallel segments, Proc. 18th Canadian Conference on Computational Geometry (CCCG), Kingston (ON), Canada (2006) 101-104.
E. Welzl, Kleinster umschliessender Kreis - Ein Demokratiebeitrag aus der Schweiz?, Algorithmus der Woche 42 (2006).
E. Welzl, Random triangulations of planar point sets, in: Algorithmic Graph Theory, Oberwolfach Reports 7 (2006) 432-435.
R. BERKE
"Deciding Relaxed Two-Colorability", Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 11, 2006).
"Relaxed Two-Coloring of Cubic Graphs", Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17, 2006).
"Deciding Relaxed Two-Colorability - A Hardness Jump", 14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 13, 2006).
B. GÄRTNER
"Linear Programming and Unique Sink Orientations",
16th Annual ACM-SIAM Symposium on Discrete Algorithms,
Miami, Florida, USA
(Jan 23, 2006).
Short course: "Linear Programming Methods",
Part of the Predoc-Course Optimization Methods in Discrete Geometry,
Technical University Berlin, Germany
(We/Th Apr 5-20, 2006).
"Simple Stochastic Games, Linear Complementarity Problems, and Unique Sink Orientations",
London School of Economics, London, Great Britain
(May 26, 2006).
"Clarkson's Randomized Linear Programming Algorithms Revisited",
Mini-Symposium on Random Discrete Structures and Algorithms,
Jahrestagung der Deutschen Mathematiker-Vereinigung,
Universität Bonn, Germany
(Sep 21, 2006).
M. HOFFMANN
"Connecting Line Segments",
Symposium Diskrete Mathematik 2006, Technical University Berlin,
Berlin, Germany
(Apr 4, 2006).
L. RÜST
"Violator Spaces: Structure and Algorithms", 14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 12, 2006).
D. SCHEDER
"Approximation Algorithms for Multi-Criteria Traveling Salesman Problems", Fourth Workshop on Approximation and Online Algorithms, ETH Zurich, Switzerland (Sep 14, 2006).
E. SCHUBERTH
"A Framework for Image-dependent Gamut Mapping",
IS&T/SPIE 18th Annual Symposium on Electronic Imaging,
San Jose, USA
(Jan 17, 2006).
"Approximate Sorting",
Latin American Theoretical Informatics Symposium (LATIN),
Valdivia, Chile
(Mar 21, 2006).
"Preference Analysis",
DIMACS Workshop on Polyhedral Combinatorics of Random Utility,
DIMACS center, Rutgers University, New Jersey
(May 24, 2006).
"Einführung in Java (Teil 2)", Schnupperstudium am Departement Informatik
ETH Zurich, Switzerland
(Aug 30 and Sep 1, 2006).
"A Kernel Approach to Gamut Boundary Determination",
14th European Signal Processing Conference (EUSIPCO),
Florence, Italy
(Sep 6, 2006).
"Psychovisuelle Tests für Parametrisierte Algorithmen",
Meeting of Departement 292,
EMPA Zurich, Switzerland
(Nov 10, 2006).
"Frauenförderung am Departement Informatik der ETH Zürich - Erfahrungen und Motivation",
Swiss ICT- KNIT,
ETH Zurich, Switzerland
(Nov 30, 2006).
T. SZABÓ
"Characters and the Projective Norm-Graphs",
Doc-Course, Harmonic Analysis in Computer Science and Combinatorics, Charles University,
Prague, Czech Republic
(Feb 16, 2006).
"Relaxed Two-Coloring of Cubic Graphs",
Theoretical Computer Science and Discrete Math Seminar, Institute for Advanced Study,
Princeton, USA
(Mar 20, 2006).
"Lower Bounds for Algorithms in Abstract Cubes",
Discrete Math and Theory of Computing Seminar, Rutgers University,
New Brunswick, USA
(Mar 23, 2006).
"Making or Avoiding Planar Graphs",
Geometry Seminar, Courant Institute, New York University,
New York City, USA
(Mar 28, 2006).
"Making, Breaking, Avoiding, Enforcing",
Discrete Mathematics Seminar, Princeton University,
Princeton, USA
(Mar 29, 2006).
"Making vs Avoiding in Positional Games",
Symposium Diskrete Mathematik 2006, Technical University Berlin,
Berlin, Germany
(Apr 3, 2006).
Short course: "Positional Games",
Trimester Programme Phenomena in high dimension, Institute Henri Poincare,
Paris, France
(Apr 24-26, 2006).
"Making vs Avoiding in Positional Games"
Workshop: Complexity of Games, Polyhedra and Lattice Points,
FIM (Institute for Mathematical Research),
ETH Zurich, Switzerland
(May 18, 2006).
"Turán's Theorem in the Hypercube",
Sixth Czech-Slovak International Symposium on Combinatorics,
Graph Theory, Algorithms and Applications,
Prague, Czech Republic
(Jul 10, 2006).
"Turán's Theorem in the Hypercube",
Horizon of Combinatorics,
Balatonalmádi, Hungary
(Jul 17, 2006).
"Relaxed Coloring of Cubic Graphs -- Extremal Graph Theory
meeting Complexity Theory",
Workshop on Combinatorics, Probability, and Computing,
Mathematisches Forschungsinstitut Oberwolfach,
Germany
(Oct 29, 2006).
"Making vs. Avoiding in Positional Games",
MHC Autumn School in Discrete Algorithms,
Seto, Japan
(Nov 15, 2006).
E. WELZL
"On the Number of Crossing-Free Matchings, (Cycles, and Partitions)",
16th Annual ACM-SIAM Symposium on Discrete Algorithms,
Miami, Florida, USA
(Jan 24, 2006).
"On the Number of Crossing-Free Configurations on Planar Point Sets",
Colloquium Combinatorics, Geometry, and Computation,
Technical University Berlin, Germany
(Jan 30, 2006).
"Random Triangulations of Planar Point Sets",
Workshop on Algorithmic Graph Theory,
Mathematisches Forschungsinstitut Oberwolfach, Germany
(Feb 14, 2006).
"On the Number of Triangulations and other Crossing-Free
Configurations on Planar Point Sets",
Discrete and Computational Geometry -- Twenty Years Later,
AMS-SIAM Summer Research Conference,
Snowbird, Utah, USA
(Jun 22, 2006; invited talk).
"Random Triangulations of Planar Points Sets",
V Jornadas de Matemática Discreta y Algorítmica (V JDMA),
Campus de Soria, Universidad de Valladolid, Spain
(Jul 13, 2006; invited talk).
"The Number of Crossing-Free Configurations on Planar Point Sets",
14th International Symposium on Graph Drawing,
Karlsruhe, Germany
(Sep 18, 2006; invited talk).
"On the Number of (and Random) Triangulations on Planar Point Sets",
Workshop on Combinatorics, Probability, and Computing,
Mathematisches Forschungsinstitut Oberwolfach,
Germany
(Nov 2, 2006).
"Lattice Triangulations",
Colloquium Methods for Discrete Structures,
Berlin Free University,
Germany
(Nov 13, 2006).
"Combinatorics of Boolean CNF Formulas",
Ramakrishna Mission Vivekananda University,
Belur Math, Howrah, West Bengal,
India
(Dec 12, 2006).
"The Number of Crossing Free Configurations on Finite Point Sets in the Plane",
26th Conference on Foundations of Software Technology and Theoretical Computer Science,
Indian Statistical Institute, Kolkata, West Bengal,
India
(Dec 13, 2006; invited talk).
R. BERKE
Teach. Assistance Graph Theory (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Teach. Assistance Coordinator.
Attended the conferences/courses/workshops:
Symposium Diskrete Mathematik, Berlin, Germany (Apr 3-4, 2006).
Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, Czech Republic (Jul 10-15, 2006).
Horizon of Combinatorics, Balatonalmádi, Hungary (Jul 17-21, 2006).
Summer School - Extremal Graph Theory and Random Graphs, Chorin, Germany (Jul 31 - Aug 4, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).
Y. BRISE
Attended the conferences/courses/workshops:
Algorithms for the SAT problem, Humboldt-Universität Berlin, Germany (Oct 27-29, 2006).
K. FISCHER
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS05/06).
K. FUKUDA
Courses taught:
"Predoc-Course: Polyhedral Computation",
Optimization Methods in Discrete Geometry, Berlin, Germany (May 17 - Jun 2, 2006).
"Discrete and Algorithmic Geometry" (with A. Prodon),
Graduate Course, EPF Lausanne, Switzerland (WS05/06).
Editor of European Journal of Combinatorics, Applied Mathematics Research eXpress.
Member of
B. GÄRTNER
Coordinator ACS.
Member of the CGAL Editorial Board.
Editor of a special issue of Computational Geometry: Theory and Applications on CGAL.
PhD examiner for Rahul Savani, London School of Economics, London, GB (Jun 26, 2006).
J. GIESEN
Program committee member of
M. HOFFMANN
Teach. Assistance Informatik (D-MATH, D-PHYS) (WS05/06).
Informatik Koordinator.
Member of the CGAL Editorial Board.
S. LAKSHMINARAYANAN
Teach. Assistance External Memory Algorithms and Data Structures (WS05/06).
D. MITSCHE
Teach. Assistance Logik (WS05/06).
Coordinator Mittagsseminar (until Mar 31).
A. RAZEN
Teach. Assistance Erfüllbarkeit logischer Formeln (WS05/06).
Teach. Assistance Extremal Combinatorics (SS06).
Coordinator Mittagsseminar (since Apr 1).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation,
Prague, Czech Republic (Feb 2 - Mar 3, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).
L. RÜST
Teach. Assistance Digitales Publizieren I: Farbwiedergabe (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Webmaster www-gremo.
Attended the conferences/courses/workshops:
Summer School on Game Theory, University of Aarhus, Denmark (Jun 26-30, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).
D. SCHEDER
Teach. Assistance Logik (WS05/06).
Teach. Assistance Seminar SAT (SS06).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation,
Prague, Czech Republic (Feb 2 - Mar 3, 2006).
E. SCHUBERTH
Teach. Assistance Algorithmische Geometrie (WS05/06).
Teach. Assistance Approximate Methods in Geometry (SS06).
Head of Frauenförderung.
Presentation of booth on Gamut Mapping and Psychovisual Tests at 25 Years of Computer Science at ETH exhibition "Die Welt zwischen 0 und 1" (Oct 20-29, 2006).
Attended the conferences/courses/workshops:
IS&T/SPIE 18th Annual Symposium on Electronic Imaging,
San Jose, USA (Jan 15-19, 2006).
Latin American Theoretical Informatics Symposium (LATIN),
Valdivia, Chile (Mar 20-24, 2006).
DIMACS Workshop on Polyhedral Combinatorics of Random Utility,
DIMACS center, Rutgers University, New Jersey (May 24-26, 2006).
14th European Signal Processing Conference (EUSIPCO),
Florence, Italy (Sep 4-8, 2006).
P. TRAXLER
Teach. Assistance Approximation: Theorie & Algorithmen (SS06).
E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.
Vice-Chair, Department of Computer Science, ETH Zurich (until Sep 30).
Program committee member of
Editorial Board member of
Member (chair, contact person) of selection committees for
Member of the EATCS Council (European Association for Theoretical Computer Science).
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.
Coreferee for habilitation of
P. ZUMSTEIN
Teach. Assistance Theory of Computing (WS05/06).
Teach. Assistance Theoretische Informatik (Kernfach) (SS06).
Attended the conferences/courses/workshops:
Doccourse Prague on Combinatorics, Geometry, and Computation,
Prague, Czech Republic (Feb 2 - Mar 3, 2006).
Summer School - Extremal Graph Theory and Random Graphs, Chorin, Germany (Jul 31 - Aug 4, 2006).
14th Annual European Symposium on Algorithms (ESA), ETH Zurich, Switzerland (Sep 11-13, 2006).
Algorithms for the SAT problem, Humboldt-Universität Berlin, Germany (Oct 27-29, 2006).
