Семинар “Алгебра и логика”
ZoomНа 16 юли 2021 г. (петък) от 13:00 часа ще се проведе дистанционно заседание на семинара по „Алгебра и логика”. Доклад на тема Proof Complexity of Resolution over linear inequalities ще изнесе Stefan Dantchev (Durham University, United Kingdom). Абстракт. 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 [...]
