Advanced Topics 5 (236 605):
Complexity of Combinatorial Counting
Detailed outline of the planned sessions available at
here
.
Actual slides (ps-files) of lectures are available
here.
Projects are listed
here.
Format: 2 hours lecture + 1 hour tirgul
Homepage:
http://www.cs.technion.ac.il/~janos/COURSES/COMBI/announce01.html
Lecturer: Prof. J.A. Makowsky
Taub 628, Tel: 4358, e-mail: janos@cs
Reception hours: Monday, 14:30-16:30
Assistant: Dr. J. Marino
Taub 619, Tel: 4873, e-mail: julian@cs
Reception hours: To be announced
Time: Sunday 13:30-16:30 (Lecture and Tirgul)
Place: Taub 401
Prerequisites:
Computability (236 343),
Graph Algorithms (234 246).
Course outline:
-
The basic problems:
Counting solutions of NP-hard problems.
Graph polynomials and their complexity.
The Tutte polynomial and
the permanent.
-
Counting classes using Turing machines.
The complexity class #P.
Complete problems for #P.
-
Valiant's algebraic circuits and the classes
VP and
VNP.
p-reductions and complete problems for
VNP.
-
Approximability of counting problems.
Course goal and requirements
Leading to the frontier of current research
in combinatorial counting.
Introducing topics for
M.Sc. and Ph.D. theses.
Projects or take home exam.
Literature
- C. Papadimitriou,
Computational Complexity,
Addison Wesley, 1994
- D.J.A. Welsh,
Complexity: Knots, Colourings and Counting,
London Mathematical Society Lecture Notes Series,
Vol. 186,
Cambridge University Press,
1993
- P. Buergisser,
Completeness and Reduction in Algebraic Complexity,
Algorithms and Computation in Mathematics, Vol. 7,
Springer, 2000
-
Additional literature from Journals is listed
here
.