Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 12, 2012

Freie Universität Berlin
Institut für Informatik
Takustraße 9
14195 Berlin Berlin
room 005

Lecture - 14:15

Bernard Chazelle - Princeton University and College de France

The Surprising Dynamics of Influence Systems

Imagine a group of interacting agents (eg, people, computers, birds, bacteria) subject to the attracting influence of the agents with which they communicate. Assume further that each agent is entitled to its own, distinct algorithm for deciding whom to listen to when.
The communication graph thus evolves endogenously in arbitrarily complex ways. We show that such an "influence system" is almost surely convergent if the communication is bidirectional and asymptotically periodic in general.
This suggests that social networks are more conducive to consensus than are older media like radio, tv, and newspapers. The proof introduces a technique of "algorithmic renormalization"likely to be of broader interest.

Colloquium - 16:00

Balazs Keszegh - Budapest

Non-crossing covering paths for planar point sets

Given a set of points, a covering path is a directed polygonal path that visits all the points. If no three points are collinear, any covering path (self-crossing or non-crossing) needs at least n/2 segments.
In both cases n-1 straight line segments obviously suffice. If the path can be self-crossing, then it is known that there exists a path with only n/2+O(n/log(n)) segments. The non-crossing case seems to be harder, we show an algorithm that finds a non-crossing covering path with at most (1-d)n segments, where d is a small constant.

joint work with Daniel Gerbner

Letzte Aktualisierung: 29.10.2012