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
Jaroslav Nesetril
Charles University, Prague (currently ETH Zurich)
Roger Wattenhofer
ETH Zurich
Ingo Wegener
Universität Dortmund
Monday, Nov 26, 2001, 14:15 - 15:45, IFW B42
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 n^{2} 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
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
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
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.
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 |