Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The Complexity of Approximate Counting
Speaker:Leslie Goldberg
coming from:University of Oxford
Speakers Bio:
Event Type:MPI Colloquium Series Distinguished Speaker
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 15 September 2014
Duration:60 Minutes
Building:E1 4

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.

Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Kurt Mehlhorn, 09/01/2014 10:50 AM -- Created document.