An online session of the Algebra and Logic Seminar will be held on July 16, 2021 (Friday) at 1:00 p.m. (UTC +3).

A talk on

Proof Complexity of Resolution over linear inequalities

will be delivered by Stefan Dantchev (Durham University, United Kingdom).

Abstract. I will start by giving a brief and non-comprehensive introduction to the general research area, Propositional Proof Complexity.

I will then focus on a specific proof system that operates on linear inequalities with integral coefficients, called Stabbing Planes (SP). Next, a general method for proving depth lower bounds in SP will be introduced, which allows us to prove logarithmic depth lower bounds for several well-studied propositional contradictions, such as the Pigeon-Hole Principle and the Ordering Principle. Finally, possible extensions and generalisations of SP will be discussed, plus some open questions.

The seminar will be held via Zoom and everyone can join at:

https://us02web.zoom.us/j/85137375021?pwd=RE5QczdFTE1xL1R6MnI2b1lkcGczQT09 

Topic: Онлайн семинар на секция “Алгебра и логика”
Time: July 16, 2021 01:00 PM Sofia
Meeting ID: 851 3737 5021
Passcode: 035647

Algebra and Logic Department, IMI-BAS
http://www.math.bas.bg/algebra/seminarAiL/
============================== =====================