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

Emo Welzl emo at
Tue May 14 11:07:08 PDT 2002

Call for Applications

                  Pre-Doc Program
         Combinatorics, Geometry, and Computation
             October 2002 -- March 2003

(At ETH Zurich; part of Berlin/Zurich Graduate
Program "Combinatorics, Geometry, and Computation")

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

Building blocks of the program are four 5-weeks research oriented
courses, a project and the preparation of a proposal for a Ph.D.; 
see schedule, speakers (including guests J. Beck, J. Bloemer,
Ch. Papadimitriou, and A. Steger) 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 master 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 Graduate
Program (although it is not automatically implied by acceptance to
the Pre-Doc program). Students who plan to continue their Ph.D. at
some other university are also welcome. Advanced diploma or master
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 assistance.

Applications with curriculum vitae, copies of certificates, thesis,
areas of interest, a letter of recommendation from the thesis
advisor should be sent to:

	Emo Welzl
	Institut Theoretische Informatik
	ETH Zentrum 
	CH-8092 Zurich  

        cgc.graduate at

Application deadline is May 31, 2002. Applicants are notified of
results about one month after the respective deadline. 
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.

RandAlgs  Randomized Algorithms
Ch. Papadimitriou (UC Berkeley; USA), E. Welzl 
(Mo&Tu, Oct 21 - Nov 22, 2002)

Randomized algorithms have by now emerged into many fields, and 
have lead to several improvements and simplifications compared to
deterministic methods. We will discuss applications in several 
areas, including optimization, approximate counting 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 

ApproxAlgs  Approximation: Theory and Algorithms
J. Bloemer, M. Cochand, T. Erlebach, B. Gaertner, A. Steger, P. Widmayer 
(Th&Fr, Oct 21 - Nov 22, 2003)

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 and derandomization;
inapproximability and the PCP concept. 

GeomMod  Surface Representations and Geometric Modeling
M. Gross 
(Mo&Tu, Jan 6 - Feb 7, 2003)

Recent advances in 3D digital geometry processing have spawned new 
generations of methods for the representation and interactive manipulation
of large scale graphics models. This course will discuss some of the 
latest developments in geometric modeling and surface representations. The
first such as splines and NURBS, and we will introduce the basic concepts 
of differential geometry. The second part of the course will address more
recent developments in geometry processing inlcuding subdivision, 
smoothing, and geometric filtering. 

PosGames  Positional Games and Algorithms
J. Beck (Rutgers University, USA) 
(Th&Fr, Jan 6 - Feb 7, 2003)

In the last few years I keep writing a book entitled `positional games', 
which would be the first book on the subject. `Positional games' is 
completely different from both the traditional Neumann-type "game 
theory" and the Berlekamp-Conway-Guy type "Nim-like games" (see the 
well-known 2-volumed `Winning Ways' of the three authors). `Positional 
games' is about `Tic-Tac-Toe-like' board games, and is closely related 
to Ramsey theory, Matching theory and the Erdos-type "probabilistic 
method" (see the well-known book of Alon-Spencer). The winning and drawing
strategies are effective potential function algorithms: this explains 
the word `algorithms' in the title. This is a brand new subject which is 
full of exciting open problems. 

The list of the subjects that we are going to cover is (1) Tic-Tac-Toe-like
games, Ramsey games, game-graph and game-tree, pairing strategy,
potential functions, (2) Game-theoretic first moment method, 
(3) Game-theoretic second moment method, (4) Graph games and random graphs, 
(5) Tic-Tac-Toe in higher dimensions, (6) Algorithmic and game-theoretic 
Lovasz Local Lemma, complexity problems. 

Prerequisites: Almost nothing -- it is a self-contained course, but a 
knowledge of the simplest concepts of combinatorics, and reasonable
problem-solving skills are expected. No textbook is available: I am 
going to give hand-outs and problem-sheets.

CompVis  Selected Topics in Computer Vision
L. van Gool, B. Schiele, G. Székely 
(Th&Fr, Jan 6 - Feb 7, 2003)

The class covers various fundamental as well as advanced techniques 
in computer vision. A particular emphasis is on visual object recognition 
using different approaches. Two alternative schools are described and 
compared: appearance vs. model based. These are complemented with novel, 
hybrid solutions, built upon invariance theory. A second emphasis is on 
techniques to characterize object shape and binary scenes. Basic concepts 
of topology and metrics on discrete image rasters are investigated. Time 
permitting, several learning techniques in the context of visual 
recognition are discussed. 

Oct 1	Reading assignments
Oct 21	Courses
-Nov 22 Mo&Tu RandAlgs
	Th&Fr ApproxAlgs
Nov 27	Exams
Nov 28	Projects, reading assignments
-Dec 19	and presentations
Jan 6	Courses
-Feb 7	Mo&Tu GeomMod
	Th&Fr PosGames  or  CompVis
Feb 12	Exams
Feb 13	Preparation of Ph.D. proposal
-Mar 28	and presentations

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