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:
- Methodologically:
To introduce the participants into active research,
concentrating on creative reading skills, and the development
of research strategies in general.
- Thematically:
To practice reserach techniques with a particular topic
where many open but challenging questions abound.
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.