Headline: teaching - colloquium CGC logo

Winter 2001/02 former semesters

Time: Mondays, 14:15 - 15:45
Location: IFW B42
(unless stated otherwise)

Organizers: CGC faculty at ETH Zurich
Contact: Emo Welzl

The CGC colloquium does not take place during the pre-doc courses. Hence, the dates available this year are the Mondays November 26, and December 3, 10, and 17, 2001.


Nov 26, 2001

Noga Alon
Tel Aviv University

Graph Property Testing


Dec 03, 2001
Jaroslav Nesetril
Charles University, Prague (currently ETH Zurich)

Colorings of Degenerated and Bounded Degree Graphs


Dec 10, 2001
Roger Wattenhofer
ETH Zurich

The TCP Congestion Control Problem


Dec 17, 2001
Ingo Wegener
Universität Dortmund

Theoretical Aspects of Evolutionary Algorithms



Monday, Nov 26, 2001, 14:15 - 15:45, IFW B42

Graph Property Testing

Noga Alon
Tel Aviv University

Let P be a property of graphs. A testing algorithm for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G on n vertices are adjacent or not, determines, with high probability, if G satisfies P or it has to be modified by deleting and adding to it at least epsilon n2 edges so that it satisfies P. After a very brief discussion of some of the known results on testable graph properties, I will describe a new result on the complexity of testing if G contains no copy of a fixed given graph H. The essence of this result is that this complexity is much lower for every bipartite graph H than it is for any non-bipartite H.


Monday, Dec 03, 2001 , 14:15 - 15:45, IFW B42

Colorings of Degenerated and Bounded Degree Graphs

Jaroslav Nesetril
Charles University, Prague (currently ETH Zurich)

We study colorings of undirected graphs in their relationship to the degrees of its vertices. For degenerated graphs we show that in the abundance of examples and from the complexity point of view (for both existence and counting problems) Brook's theorem and the First-Fit algorithm are the only easy cases. However for bounded degree graphs corresponding questions are far from being solved and even the following simple "Pentagon Problem" is presently open:

Is it true that any cubic graph G with a sufficiently large girth can be properly colored by 4 colors {0,1,2,3,4} such that the only difference on its edges is either +1 or -1 (mod 5)?

Relevant results will be surveyed.

(A K-degenerated graph is a graph the vertices of which can be linearly ordered such that each vertex has at most K edges to the left.)


Monday, Dec 10, 2001 , 14:15 - 15:45, IFW B42

The TCP Congestion Control Problem

Roger Wattenhofer
ETH Zurich

Internet standards such as TCP have been proposed and widely deployed without seeking advice from theoreticians, that is, without formal efficiency analysis. In this talk we will discuss the TCP congestion control mechanism from an algorithmic viewpoint. We will reduce congestion control to an algorithmic online problem: How many packets per time slot can a sender transmit to a receiver before the network gets congested and starts to drop packets? What happens if the network bandwidth between sender and receiver changes over time? Surprisingly, our asymptotically optimal results are not very far from the TCP congestion control specification.


Monday, Dec 17, 2001 , 14:15 - 15:45, IFW B42

Theoretical Aspects of Evolutionary Algorithms

Ingo Wegener
Universität Dortmund

Efficient algorithms should have a good performance guarantee for the expected run time and the quality of the solution. For a long time algorithms without such performance guarantees were not be considered as really efficient. However, nowadays randomized search heuristics have many successful applications. It is difficult to analyse these heuristics. One reason is that they are not designed to support such an analysis. In order to understand and to improve randomized search heuristics it is necessary to set up a theory on these heuristics containing results on the expected optimization time for selected problems and classes of functions. It will be shown how such a theory can be developed. Example results show which methods can be applied and which problems have to be solved in the future.


Former semesters

Summer 2001 , Winter 2000/01 , Summer 2000 , Winter 1999/2000 , Summer 1999 , Winter 1998/99 , Summer 1998 , Winter 1997/98 , Summer 1997


Last modified on 2001-12-04 22:45:47 by Falk Tschirschnitz <tschirsc@inf.ethz.ch>      Copyright © 2000-2001 CGC
!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!