Abstract: Exact combinatorial counting problems are most usually P-hard. Approximation is somewhat easier, but techniques for proving both positive and negative results are limited. We will review work in this area, including a recent attempt to classify the complexity of some approximate counting problems.
Kolloquium - 16 Uhr s.t.
Abstract: Helly's theorem (1913) states that for any finite collection of convex sets in d-dimensional space we can conclude that their intersection is non-empty if we know that the intersection of any d of the sets is non-empty. Generalizations exist in various directions, mostly still dealing with convex sets. We survey generalizations applied to non-convex sets and present new results.