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:Fine-grained dichotomies for the Tutte plane and Boolean #CSP
Speaker:Cornelius Brand
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 2 August 2016
Duration:30 Minutes
Building:E1 4

Jaeger, Vertigan, and Welsh proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén and Husfeldt and Taslaman, in combination with Curticapean, extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line y=1, which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given n-vertex graph cannot be determined in time exp(o(n)) unless #ETH fails.

Another dichotomy theorem we strengthen is the one of Creignou and Hermann for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that all #P-hard cases are also hard under #ETH. The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp(o(n)) unless #ETH fails. In order to prove our results, we use the block interpolation idea by Curticapean and transfer it to systems of linear equations that might not directly correspond to interpolation.

joint work with Holger Dell and Marc Roth

Name(s):Holger Dell
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created by:Holger Dell, 07/28/2016 02:28 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Holger Dell, 07/28/2016 02:29 PM
  • Holger Dell, 07/28/2016 02:28 PM -- Created document.