Victor Lagerkvist

The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems


I will present results and ongoing research on the algebraic approach towards studying fine-grained complexity of (primarily NP-hard) constraint satisfaction problems (CSPs). In a nutshell, fine-grained complexity is the study of sharp upper and lower bounds with respect to the complexity parameter $n$, the number of variables. This is typically carried out in the light of conjectures such as the exponential-time hypothesis (ETH) and its stronger variant (SETH). For SAT and CSP such precise lower bounds have proven extremely elusive, and except for trivial cases, effectively no such sharp lower bounds were known. We successfully achieve strong lower bounds under the SETH by employing an algebraic framework where we study constraint languages $\Gamma$ in terms of their algebraic properties. We uncover a powerful algebraic framework where a mild restriction on the allowed constraints offers a concise algebraic charactebrization. On the relational side we restrict ourselves to Boolean languages closed under variable negation and partial assignment, called sign-symmetric languages. On the algebraic side this results in a description via partial operations arising from system of identities, with a close connection to operations resulting in tractable CSPs, such as near unanimity operations and edge operations. Using this connection we construct improved algorithms for several interesting classes of sign-symmetric languages, and prove explicit lower bounds under SETH. Thus, we find the first example of an NP-complete SAT problem with a non-trivial algorithm which also admits a non-trivial lower bound under SETH. This suggests a dichotomy conjecture with a close connection to the CSP dichotomy theorem: an NP-complete SAT problem admits an improved algorithm if and only if it admits a non-trivial partial invariant of the above form.

Recording of the talk (Passcode: ‘t2!Lrw3I’)