Graduate Theory Research Seminar (238900)

Spring semester 2007
Page under construction, last updated: 14.03.2007

Complexity of Counting


Literature for the seminar. Sessions of the seminar.

For whom this seminar is meant?

For graduate students with an interest in the theory of computability and complexity. Undergraduates may attend only with special permission of the lecturer.

For those graduate students who have already taken 238900 before,
but on another topic, arrangements will be found to get credit again.


Lecturer: Prof. J.A. Makowsky and participants
Time: Tuesday, 16:30-18:30
Place: Taub 201
Prerequisites: Computability, some elementary graph theory,
some familiarity with linear and abstract algebra.
Format: Two hours frontal presentations.
Requirements: Edited version of frontal presentation or final project.

Purpose of the seminar

The purpose of the seminar is twofold:

Outline

Counting functions, numeric graph invariants and graph polynomials

Counting functions count combinatorial objects, such as the number of k-colorings, the number of satisfying assignments, the number of hamiltonian circuits, etc. They may also count the number of graphs of size n having a certain graph property. Generalization of counting problems are graph polynomials, and more generally, parametrized numeric graph invariants.

Counting problems are notoriously difficult. Valiant introduced the complexity class #P, which will be at the center of our attention. However, not all aspects of counting problems and their generalizations, are well captured in Valiant's framework.

The seminar will try to develop a comprehensive complexity theory for parametrized numeric graph inviariants.

Reducibilities between counting function

Complexity theory of counting functions

Towards an complexity theory of numeric graph invariants


Literature for the seminar. Sessions of the seminar.