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