MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction

Marvin Künnemann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, INET, AG 5, SWS  
AG Audience
English

Date, Time and Location

Tuesday, 7 July 2020
13:00
30 Minutes
virtual
virtual
Saarbrücken

Abstract

To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean constraint satisfaction with size constraint exactly k. More precisely, we aim to determine, for any finite constraint family, the optimal running time f(k) n^{g(k)} required to find satisfying assignments that set precisely k of the n variables to 1.


Under central hardness assumptions on detecting cliques in (hyper-)graphs, we give an almost tight characterization of g(k) into four regimes, giving a more fine-grained perspective than a previous FPT/W[1]-hardness dichotomy (Marx, Computational Complexity 2005). Our most interesting technical contribution is a subexponential-in-k algorithm for SubsetSum with precedence constraints parameterized by the target k -- particularly the approach, based on generalizing a bound on the Frobenius coin problem to a setting with precedence constraints, might be of independent interest.

This is joint work with Daniel Marx, appearing at CCC 2020 (https://arxiv.org/abs/2005.11541)

Contact

Marvin Künnemann
+49 681 9325 1025
--email hidden

Tags, Category, Keywords and additional notes

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Marvin Künnemann, 06/26/2020 02:54 PM
Marvin Künnemann, 06/26/2020 02:52 PM -- Created document.