November 3 , 2007
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 26
12489 Berlin
room 1'305
Lecture - 14:15
Abstract:
The theory of positional games is a branch of combinatorics,
whose main aim is to develop systematically an extensive
mathematical basis for a variety of two player perfect
information games, ranging from such commonly popular games as
Tic-Tac-Toe and Hex to purely abstract games played on graphs
and hypergraphs.
In this talk I will survey basic notions and concepts of
positional games and some recent developments in the field,
putting an emphasis on interconnections between positional games
and other branches of mathematics and computer science, in
particular probabilistic considerations.
Colloquium - 16:00
Abstract:
The Exponential Time Hypothesis (ETH) says that there is a constant c>1
such that deciding the satisfiability of n-variable 3-CNF formulas
requires time at least c^n. We introduce the weaker counting version of
this hypothesis (#ETH), namely that every algorithm that computes the
number of satisfying assignments requires time c^n, and we establish a
sparsification lemma for this hypothesis.
Under this hypothesis, we show a number of lower bounds for well-studied
#P-hard counting problems: Computing the permanent of an n x n matrix
requires time c^n. Restricted to 01-matrices, our bound is c^{n/log n}.
For multigraphs with n vertices, computing the Tutte polynomial
requires time c^n at points (x,y) with either (x-1)(y-1) != 1 and y !=
-1,0,1 or x != -1,0,1 and y=0. The proofs use beautiful combinatorial
properties of the investigated objects.