#
Monday Lecture and Colloquium

**November 3 , 2007 **

Humboldt-Universität zu Berlin

Institut für Informatik

Rudower Chaussee 26

12489 Berlin

room 1'305

** Lecture - 14:15**

###
Michael Krivelevich, Tel Aviv University

###
Positional games

*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**

### Holger Dell, Humboldt Universität Berlin

### Exponential Time Complexity of the Permanent and the Tutte Polynomial

*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.

Letzte Aktualisierung:
22.10.2008