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

[Emo Welzl]

First Call for Applications

                    Pre-Doc Program
          Combinatorics, Geometry, and Computation
               October 2000 -- March 2001


(At ETH Zurich; part of Berlin/Zurich European 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; Algorithms 
Design, Analysis and Implementation; Optimization and 
Mathematical Programming.

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 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/Z"urich 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 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 assistance.

Applications with curriculum vitae, copies of certificates, 
theses, 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         
	Switzerland

(Applications that arrive before before May 19 will be notified 
of acceptance by June 5. There is a second round with deadline
June 16 with notification July 3.)

For further information use tel: ++41-1-63 273 92, 
email <emo at inf.ethz.ch>, or 
<http://www.inf.ethz.ch/cgc/> (starting May 4). 


SCHEDULE
(Courses, lecturers, and abstracts below)
---------------------------------------
Oct 1	Reading assignments
---------------------------------------
Oct 23	Courses
-Nov 24 Mo&Tu RandAlgs
	Th&Fr CombGeom
Nov 27	Exams
---------------------------------------
Nov 30	Projects, reading assignments
-Dec 20	and presentations
---------------------------------------
Jan 8	Courses
-Feb 9	Mo&Tu GraphVis
	Th&Fr ApproxAlgs
Feb 12	Exams
---------------------------------------
Feb 15	Preparation of Ph.D. proposal
-Mar 31	and presentations
---------------------------------------

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 
	(Emo Welzl)

	Randomized algorithms have by now emerged in many fields,
	and have lead to several improvements compared to 
	determinisitic methods. We will discuss several basic methods
	in several areas, including graph algorithms and geometry, 
	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.

CombGeom 	
	Combinatorial Geometry 
	(Komei Fukuda, Juergen Richter-Gebert)

	Geometric objects (like polytopes or arrangements of 
	hyperplanes) carry two layers of information. First of all 
	they are described by the coordinates of the parts involved. 
	On the other hand there is also a combinatorial description 
	that cares only about the relative position of the elements. 
	This course is about the subtle interplay of coordinates and
	combinatorics. We introduce the "theory of oriented matroids"
	as the primary framework for the study. This theory allows
	us to get deep structural insight in topics like "polytope 
	theory", "linear optimization", "automatic geometric theorem 
	proving", "quasicrystals" and many more.

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

	Although being two separate disciplines we observe that 
	Graphics and Vision are increasingly converging. Methods and 
	algorithms developed independently are more and more getting 
	combined or merged to 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 consisting of 
	lectures and practical or theoretical exercises.

ApproxAlgs	
	Approximation: Theory and Algorithms
	(Johannes Bloemer, Maurice Cochand, Bernd Gaertner, 
	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
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://uiuc.edu/~sariel/CG/compgeom/maillist.html.