Lower bounds for lift-and-project proof systems

点击翻译按钮获取中文摘要

The general research of this project is Propositional Proof Complexity. The main objective is proving lower bounds, both on the degree and the size, of proofs written in a formal system called Sum of Squares (SoS). Up to now, very few such lower bounds have been proven, and mainly for rather unnatural statements. We intend to apply some standard machinery from probabilistic combinatorics as well as from model theory in order to prove results about natural combinatorial principles such as the pigeon-hole principle and the least-number principle where symmetry plays a crucial role. Our results will have some consequences in an area of optimisation known as semi-definite programming.The relevant research areas are Logic and Combinatorics and Theoretical Computer Science