Lower bounds for lift-and-project proof systems

本课题一般研究的是命题证明的复杂性。主要目的是证明在一种称为平方和(SOS)的形式系统中编写的证明的次数和大小的下界。到目前为止，很少有这样的下限被证明，而且主要是针对相当不自然的陈述。我们打算应用概率组合学和模型理论中的一些标准机制来证明关于自然组合原理的结果，如鸽子洞原理和最小数原理，其中对称性起着关键作用。我们的结果将在一个被称为半定规划的最优化领域产生一些结果。相关的研究领域是逻辑与组合学和理论计算机科学

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