Pre-Doc Program in "Combinatorics, Geometry, and Computation", ETH Zurich
Emo Welzl
emo at inf.ethz.ch
Tue May 14 11:07:08 PDT 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 deadline is May 31, 2002. Applicants are notified of
results about one month after the respective deadline.
----------------------------------------------------------------
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.
---------
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.
---------------------------------------
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 or CompVis
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