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

Emo Welzl emo at inf.ethz.ch
Tue Feb 12 12:32:19 PST 2002


Call for Applications

                  Pre-Doc Program
         Combinatorics, Geometry, and Computation
             October 2002 -- March 2003
               http://www.cgc.ethz.ch/


(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  
	Switzerland

        cgc.graduate at inf.ethz.ch


Application deadlines are Mar 22, 2002, and May 31, 2002. 
Applicants are 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 also for those who fulfill the necessary prerequisites 
only at a later stage.
 
----------------------------------------------------------------
COURSES
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 
situations. 

---------
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.

---------------------------------------
SCHEDULE
---------------------------------------
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
Feb 12	Exams
---------------------------------------
Feb 13	Preparation of Ph.D. proposal
-Mar 28	and presentations
---------------------------------------

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.



More information about the Compgeom-announce mailing list