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 Difficulty of Achieving (Abstract) Satisfaction
Speaker:Martin Brain
coming from:University of Oxford
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Thursday, 29 September 2016
Duration:60 Minutes
Building:E1 4
A small amount of practical experience with SAT, SMT or CSP solvers (or
any tool that uses them, such as most verification systems) will show
that there is significant variation in run-time even between relatively
similar problems. This naturally leads to a whole range of questions;
What is difficulty? Where does it come from? What is the relation
between theoretical measures (such as proof complexity) and practical
ones (such as run-time)? Can we recognise difficulty and identify it
with parts of the problem? Can we predict the difficulty of a problem
in less time than it takes to solve it? In this talk we will present an
abstract satisfaction view on difficulty; using the mathematics of
abstract interpretation to understand satisfiability problems. This is
a work-in-progress talk so all are welcome to attend and participate.
Name(s):Jennifer Müller
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Jennifer Müller/MPI-INF, 09/13/2016 11:17 AM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Jennifer Müller, 09/27/2016 02:58 PM
  • Jennifer Müller, 09/13/2016 11:19 AM -- Created document.