Winter 2001/02

former semesters

Pre-Doc Courses

Students who are interested in participating in these pre-doc courses have to contact the instructors before-hand (some of the courses come with preceding reading assignments).

RandAlgs  Randomized Algorithms
E. Welzl
(Mo&Tu, Oct 22 - Nov 23, 2001)

Randomized algorithms have by now emerged in many fields, and have lead to several improvements compared to deterministic 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.

Additional information

TopCoGe  Topological Methods in Combinatorics and Geometry
J. Matousek
(Th&Fr, Oct 22 - Nov 23, 2001)

One of the important tools for proving results in discrete mathematics are theorems from algebraic topology, most notably various fixed-point theorems. The course covers the basic topological notions and results (simplicial complexes, Borsuk-Ulam theorem and its generalizations etc.) and proofs of several combinatorial and geometric results. The topological notions and results are kept on very elementary level. In particular, knowledge of elementary algebraic topology, like introductory homology theory, is (encouraged but) not required.

Additional information

GraphVis  Advanced Topics in Vision and Graphics
L. van Gool, D. Hall, A. Keller, G. Székely
(Mo&Tu, Jan 7 - Feb 8, 2002)

Although being two separate disciplines we observe that Graphics and Vision are increasingly converging. Independently developed methods and algorithms are being combined and merged into 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 consists of lectures and practical or theoretical exercises.

Additional information

ApproxAlgs  Approximation: Theory and Algorithms
J. Blömer, M. Cochand, T. Erlebach, B. Gärtner, A. Steger, P. Widmayer
(Th&Fr, Jan 7 - Feb 8, 2002)

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.

Additional information

Courses are held in the language given by the abstract. Please note, that the descriptions are still tentative.

Pseudorandomness and Algebraic Methods in Combinatorics and Algorithms   
T. Szabo
(We 13-15 [Exercises: We 15-16])

Pseudorandom structures possess some level of randomness, which could be just enough in certain applications while saving random bits. In the course we discuss combinatorial aspects of pseudorandomness, mostly in graphs, with some applications to algorithms. As there is a strong connection between pseudorandom properties and eigenvalues of a graph, our methods include linear algebra. Other topics considered: Shannon capacity of graphs, constructive Ramsey-theory, combinatorial Nullstellensatz, intersection theorems and their applications, etc. Some basic knowledge of algebra and discrete probability is helpful but not essential.

Algorithmen für Kommunikationsnetze   
T. Erlebach
(Mo 10-12, ETZ G78.1 [Exercises: Mi 15-17, ETZ G91])

Grundlagen zu Algorithmen und Graphen (Spannbäume, kürzeste Pfade, Flussprobleme); effiziente Algorithmen für optimal lösbare Probleme (z.B. Multicast in WDM-Netzen); effiziente Datenstrukturen (z.B. Lookup-Table im IP-Router); Approximationsalgorithmen für Netzwerkoptimierungsprobleme (z.B. Lastbalancierung in Ringen, Wellenlängenzuteilung in WDM-Netzen, Ausfallsicherung von Netzen); Online-Algorithmen, die trotz fehlendem Wissen über die Zukunft gute Entscheidungen treffen (z.B. Zugangskontrolle in QoS-Netzen).

Additional information

In many instances of combinatorial problems one studies special maps and correspondences which are tailored to capture a variety of discrete phaenomena. Structural combinatoriics studies such situations and stresses their relationaship to the mainstream mathematics (model theory, algebra and probability in particular). This will be a self-contained course based on a forthcoming book.

The tentative contents:
1. Mappings and Categories (Basic examples, concreteness as the only combinatorial obstacle -Freyd Vinarek Theorem)
2. Existence vrs. Counting (Reconstruction, cancellation in finite structures, Lovasz, Muller theorems, polynomials via maps)
3. Homomorphisms, tensions and flows (continuous and matroid setting, rich quasiorders)
4. Constructions (Product classes, dimension, LA method, product conjecture, applications, extension properties)
5. Coloring Order (density, independence, countable universality, bounds for minor closed families, countable graphs)
6. Homomorphism dualities (algorithmic and extremal aspects, Gallai-Roy type theorems)
7.Amalgamation and Combinatorial Sieve (density, sparse graphs, Ramsey theory).

Additional information

WEB Algorithms   
P.Penna, R. Wattenhofer, P. Widmayer
(We 15-17, IFW A34 [Exercises: We 14-15, IFW A34])

The goal of the course is to understand the main algorithmic issues and techniques related to the Web*. Traditionally an "algorithm" is a computational procedure that takes an input and produces an output. A "Web algorithm" is different because the Web is distributed and dynamically changing. More importantly, not all entities in the Web cooperate; some act selfishly and spontaneously. How much performance is lost because of this? And what can we do about it? To answer these questions, we need a theoretical model for the Web that describes how the participating entities interact and react to a changing situation.

We discuss recent advances in this new research area that highlights links between different research topics such as Game Theory, Economy, Web Research, and Theoretical Computer Science. One of the goals of this course is to provide different perspectives for a problem. Towards this end we will consider routing, networking, and graphs problems in different settings. For instance:

Online algorithms capture the lack of performance due to uncertainty about the future: e.g. we need to decide how to route a stream of packets without knowledge of future routing requests.

Algorithms for selfish agents study how to design a protocol in the case where agents that implement the protocol may follow their own interests, and tune the parameters of the protocol for their own benefit: e.g. what happens if a selfish Internet user increases her TCP window size to get more throughput?

*Remark: In this announcement we use a generic term "Web" for all layers of the Internet: From basic router protocols to applications such as the World Wide Web.

The concept of graphs and their properties proved to be essential not only in the combinatorial theory but also in certain areas of algebra, probability, geometry and computational complexity. They also provide useful models in such diverse areas of science as electrical and communication networks, chemistry and biology.

Graph theory is one part of discrete mathematics which has already developed into a theory on its own with its deep structural results, minimax theorems and so on. The aim of this course is to introduce the most important concepts and results of this theory, and connect it, whenever possible, to different areas of classical mathematics.

The course is planned to cover, besides the basics, the following topics: Bipartite graphs and factors of graphs. Connectivity, cuts and flows in networks. Graph colourings, independent sets and chromatic number, perfect graphs. Extremal graph theory and Ramsey theory. Geometric representation of graphs, planar graphs and graph drawings. Applications to incidence geometry and additive number theory. Graphs, matrices and determinants, applications to difficult enumeration problems, such as number of rhombic tilings. Random graphs and probabilistic methods, Lovasz local lemma, Szemeredi's regularity. Group theoretic aspects, regular graphs, spectra of graphs, expanding properties, graph automorphisms.

Additional information

Former semesters

Winter 2000/01 , Summer 2001

Last modified on 2002-02-05 17:22:50 by Falk Tschirschnitz <tschirsc@inf.ethz.ch>

Copyright © 2000-2001