MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

The Complexity of Approximate Counting

Leslie Goldberg
University of Oxford
MPI Colloquium Series Distinguished Speaker
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Monday, 15 September 2014
11:00
60 Minutes
E1 4
024
Saarbrücken

Abstract

Title: The Complexity of Approximate Counting

Abstract: Computational counting problems
arise in applications such as statistics, statistical physics, coding, and machine learning.
In such a problem, a numerical quantity (a weighted sum) is computed, either exactly or approximately. Examples include computing (or estimating) an integral, a probability, or the expectation of a random variable.
Work in computational complexity aims to understand the intrinsic nature
of these problems, discovering which are inherently feasible and which are inherently infeasible.
I will survey what is known about the complexity of counting problems, focussing especially on approximate counting.
Completely classifying
the complexity of all such problems is well
beyond the scope of what we can do today, but progress is being made
in widely-applicable domains such as counting constraint satisfaction problems
and graph homomorphism problems.

Contact

Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only

Kurt Mehlhorn, 09/01/2014 10:50 -- Created document.