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

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

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

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