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
The relevant research areas are Logic and Combinatorics and Theoretical Computer Science
Organisations
People |
ORCID iD |
Stefan Dantchev (Primary Supervisor) | |
Abdul Ghani (Student) |
Studentship Projects
Project Reference | Relationship | Related To | Start | End | Student Name |
---|---|---|---|---|---|
EP/R513039/1 | 30/09/2018 | 29/09/2023 | |||
2115321 | Studentship | EP/R513039/1 | 30/09/2018 | 30/03/2022 | Abdul Ghani |