Monday, January 28, 2013
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
Many important problems in mathematics and its applications are modeled using linear constraints respectively polyhedra. Standard modeling often yields polyhedra having many symmetries. However, standard algorithms do not take advantage of them, and even worse, they often work particularly poorly on symmetric problems. In this talk we give an overview about ongoing work on new symmetry exploiting techniques for three fundamental task in polyhedral computations: the representation conversion problem, integer linear programming and lattice point counting. Initial proof-of-concept results show that affine symmetries can be exploited quite well in certain situations. In order to apply these new techniques on a broader scale new theoretical grounds have to be broken.
Colloquium - 16:00
A Maker-Breaker game is defined as follows: Given a board X and a subset F of its power set (called the set of winning sets), the two players Maker and Breaker alternately claim elements of X. If Maker occupies an element of F completely during the game, she wins. Otherwise, Breaker is called the winner.
Because of their relation to strong games, fast winning strategies for Maker are of special interest. We will discuss the mentioned relation. Moreover, we will see some recent results concerning fast strategies in Maker-Breaker games played on complete and on sparse random graphs.
Joint work with Asaf Ferber, Roman Glebov, Dan Hefetz, Michael Krivelevich and Anita Liebenau