The ACO Seminar (2015–2016)

Algebraic and semi-algebraic proof systems make a very important part of the modern proof complexity. They explore the possibility of proving meaningful statements expressed as propositional tautologies using algebra and geometry in addition to logic. More specifically, based on the powerful Nullstellensatz/Positivestellensatz theorems, these systems manipulate with polynomial equations or inequalities rather than with logical formulas. This area is extremely well connected to other branches of theory of computing and mathematics, notably to approximation algorithms in combinatorial optimization, and it is growing fast.

The talk will consist of two parts. First, we will give a general overview of the area and explain some of the connections mentioned above. In the second, more technical, part we will talk about a very recent paper on the width of semi-algebraic proofs in dynamical proof systems.