Size bounds for algebraic and semialgebraic proof systems 

Hakoniemi, Tuomas (Data de defensa: 2022-03-25)

This thesis concerns the proof complexity of algebraic and semialgebraic proof systems Polynomial Calculus, Sums-of-Squares and Sherali-Adams. The most studied complexity measure for these systems is the degree of ...