Pre-Doc Program - Combinatorics, Geometry, and Computation - ETH Zurich

Emo Welzl emo at
Tue Dec 12 16:53:27 PST 2000

First Call for Applications

                    Pre-Doc Program
        Combinatorics, Geometry, and Computation (CGC)
               October 2001 -- March 2002

(At ETH Zurich -- part of Berlin/Zurich CGC Graduate Program)

ETH Zurich offers a one-semester study program that focuses on 
the preparation of a Ph.D. in areas like: Discrete and Computational 
Geometry; Computer Graphics and Vision; Algorithms Design, Analysis 
and Implementation; Optimization and Mathematical Programming.

Building blocks of the program are four 5-week research oriented
courses, a project and the preparation of a proposal for a Ph.D. 
(see schedule and topics below).

ETH offers a limited number of scholarships of Sfr 2'200 per month 
(for a six months period) for students with a Diploma or Masters in 
a field related to the topics of the program (including computer 
science, mathematics, electrical engineering, and physics). There is 
a possibility of continuing a Ph.D. in the Berlin/Zurich CGC Graduate 
Program (although it is not automatically implied by acceptance to the 
PreDoc program). Students who plan to continue their Ph.D. at some 
other university, or are in the course of doing a Ph.D., are also 
welcome. Advanced Diploma or Masters students can be considered for a 
one-semester exchange program as well, if a feasible arrangement with 
their home universities can be made.

The language of the program is English. The program is open to 
applicants of all nationalities.

Students who receive a scholarship are expected to provide teaching 

Applications with curriculum vitae, copies of certificates, 
(diploma/masters) thesis, areas of interest, a letter of 
recommendation of the last advisor, should be sent to:

	Emo Welzl
	Institut Theoretische Informatik
	ETH Zentrum 
	CH-8092 Zurich         

Application deadlines are Jan 19, 2001, Mar 23, 2001, and May 30, 2001; 
last deadline dependent on availability. Applicants will be notified of
results about one month after the respective deadline. This stepwise
procedure allows students to obtain a commitment at an early stage,
while leaving some options for those who fulfill the necessary
prerequisites only at a later stage.

For further information consult the web page of the Berlin/Zurich CGC 
Graduate Program <> or email 
<cgc.predoc at>. 


SCHEDULE 2001/2002
(Courses, lecturers, and abstracts below)
Oct 1	Reading assignments
Oct 22	Courses
-Nov 23 Mo&Tu RandAlgs
	Th&Fr TopCoGe
Nov 29	Projects, reading assignments
-Dec 19	and presentations
Jan 7	Courses
-Feb 8	Mo&Tu GraphVis
	Th&Fr ApproxAlgs
Feb 14	Preparation of Ph.D. proposal
-Mar 28	and presentations

Courses will be held two days a week, for a five-weeks period.
As a rough framework, every day includes 3 hours of lectures,
exercises in groups, and a discussion of exercises.

	Randomized Algorithms 
	(Emo Welzl)

	Randomized algorithms have by now emerged in many fields,
	and have lead to several improvements compared to 
	deterministic methods. We will discuss several basic methods
	in several areas, including graph algorithms and geometry, 
	optimization, discrepancy, and solving of hard problems (e.g. 
	SAT). The emphasis will be on understanding of the basic 
	methods, so that they can be applied in several situations.

	Topological methods in combinatorics and geometry
	(Jiri Matousek)

	One of the important tools for proving results in discrete 
	mathematics are theorems from algebraic topology, most notably 
	various fixed-point theorems. The course covers the basic 
	topological notions and results (simplicial complexes, 
	Borsuk-Ulam theorem and its generalizations etc.) and proofs 
	of several combinatorial and geometric results. The topological 
	notions and results are kept on very elementary level. In
	particular, knowledge of elementary algebraic topology, like
	introductory homology theory, is (encouraged but) not required.

	Advanced Topics in Vision and Graphics
	(Luc van Gool, Markus Gross, Bernt Schiele, Gabor Szekely)

	Although being two separate disciplines we observe that 
	Graphics and Vision are increasingly converging. Independently
	developed methods and algorithms are being combined and merged 
	into sophisticated frameworks covering a wide range of 
	applications. In this course we will present a selection of 
	advanced topics in Vision and Graphics illustrating the tight 
	relationship between the two disciplines. We will discuss
	recent research results and developments in both areas with 
	a special emphasis on modeling and geometry. Topics include 
	the notion of invariance, methods for 3D reconstruction,
	learning and statistical modeling, mesh signal processing, 
	image based rendering, deformable templates and FEM. The course 
	will be organized into separate modules each of which consists 
	of lectures and practical or theoretical exercises.

	Approximation: Theory and Algorithms
	(Johannes Bloemer, Maurice Cochand, Thomas Erlebach, 
	Bernd Gaertner, Angelika Steger, Peter Widmayer)

	This course is concerned with approximation algorithms for
	NP-hard optimization problems. The topics covered include:
	basic and advanced approximation algorithms for selected 
	problems; more general techniques such as linear programming
	relaxation, derandomization, and semidefinite programming;
	inapproximability and the PCP concept.

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list