Lower bounds for lift-and-project proof systems

Lead Research Organisation: Durham University
Department Name: Computer Science

Abstract

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

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/R513039/1 01/10/2018 30/09/2023
2115321 Studentship EP/R513039/1 01/10/2018 31/03/2022 Abdul Aziz Ghani