Colloquium: Reasoning in propositional logic using Gröbner bases
Plats: Hörmander lecture hall
Kontakt: kalle [at] maths [dot] lth [dot] se
Spara händelsen till din kalender
Jakob Nordström from KTH talks at the Colloquium on 'Reasoning in propositional logic using Gröbner bases'
Given a formula in propositional logic, is it possible to determine efficiently whether it has a satisfying assignment or not? This seemingly simple question is one of the well-known Millennium Prize Problems proposed as major challenges for modern mathematics. In it most general formulation the problem still appears to be completely out of reach, but since the 1970s researchers in computational complexity theory have obtained results in many concrete computational models.
In this talk we will discuss how algebraic methods using Gröbner bases can be applied to solve logic formulas, and present techniques for proving lower bounds (impossibility results) for what such algorithms can achieve. Time permitting, we will also sketch how these techniques can be used to prove strong lower bounds for the state-of-the-art graph colouring algorithms presented in a sequence of papers by De Loera et al. No prerequisites are assumed, and we will quickly recap the basics needed from propositional logic and abstract algebra.
This presentation is based on joint work with Mladen Miksa and Massimo Lauria.
For more information on the speaker, Jakob Nordström, bio and publications, see