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). 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
(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.)
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ó
(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.)
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
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.
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.
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.
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).
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
Editorial Board member of
Member (chair, contact person) of selection committees for
Coreferee for dissertations of
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).