{"id":{"repo_id":"durham","oai_identifier":"oai:etheses.durham.ac.uk:191"},"canonical_url":"https://search.dev.ndltd.org/etd/durham/oai:etheses.durham.ac.uk:191","repository":{"repo_id":"durham","name":"Durham University","base_url":"http://etheses.dur.ac.uk/cgi/oai2"},"display":{"title":"Rank Lower Bounds in Propositional Proof Systems Based on Integer Linear Programming Methods","abstract":"The work of this thesis is in the area of proof complexity, an area which looks to uncover the limitations of proof systems. In this thesis we investigate the rank complexity of tautologies for several of the most important proof systems based on integer linear programming methods. The three main contributions of this thesis are as follows: Firstly we develop the first rank lower bounds for the proof system based on the Sherali-Adams operator and show that both the Pigeonhole and Least Number Principles require linear rank in this system. We also demonstrate a link between the complexity measures of Sherali-Adams rank and Resolution width. Secondly we present a novel method for deriving rank lower bounds in the well-studied Cutting Planes proof system. We use this technique to show that the Cutting Plane rank of the Pigeonhole Principle is logarithmic. Finally we separate the complexity measures of Resolution width and Sherali-Adams rank from the complexity measures of Lovasz and Schrijver rank and Cutting Planes rank.","abstract_html":"The work of this thesis is in the area of proof complexity, an area which looks to uncover the limitations of proof systems. In this thesis we investigate the rank complexity of tautologies for several of the most important proof systems based on integer linear programming methods. The three main contributions of this thesis are as follows: Firstly we develop the first rank lower bounds for the proof system based on the Sherali-Adams operator and show that both the Pigeonhole and Least Number Principles require linear rank in this system. We also demonstrate a link between the complexity measures of Sherali-Adams rank and Resolution width. Secondly we present a novel method for deriving rank lower bounds in the well-studied Cutting Planes proof system. We use this technique to show that the Cutting Plane rank of the Pigeonhole Principle is logarithmic. Finally we separate the complexity measures of Resolution width and Sherali-Adams rank from the complexity measures of Lovasz and Schrijver rank and Cutting Planes rank.","abstract_has_math":false,"creators":["Rhodes, Mark Nicholascharles"],"institution":"Durham University","degree_name":"PhD","degree_level":"doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-07-24T02:11:04Z","subjects":[],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Rhodes, Mark Nicholascharles"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Engineering and Computing Science, School of (2008-2017)"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["Durham University"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://etheses.durham.ac.uk/id/eprint/191/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["PhD"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://etheses.durham.ac.uk/id/eprint/191/1/thesis_mark.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The work of this thesis is in the area of proof complexity, an area which looks to uncover the limitations of proof systems. In this thesis we investigate the rank complexity of tautologies for several of the most important proof systems based on integer linear programming methods. The three main contributions of this thesis are as follows: Firstly we develop the first rank lower bounds for the proof system based on the Sherali-Adams operator and show that both the Pigeonhole and Least Number Principles require linear rank in this system. We also demonstrate a link between the complexity measures of Sherali-Adams rank and Resolution width. Secondly we present a novel method for deriving rank lower bounds in the well-studied Cutting Planes proof system. We use this technique to show that the Cutting Plane rank of the Pigeonhole Principle is logarithmic. Finally we separate the complexity measures of Resolution width and Sherali-Adams rank from the complexity measures of Lovasz and Schrijver rank and Cutting Planes rank."]},{"key":"dc:format","label":"Dc Format","values":["text"]},{"key":"dc:title","label":"Title","values":["Rank Lower Bounds in Propositional Proof Systems Based on Integer Linear Programming Methods"]}]}],"canonical_facts":{"dc:creator":["Rhodes, Mark Nicholascharles"],"dc:date":["2009"],"dc:date.issued":["2009"],"dc:description.abstract":["The work of this thesis is in the area of proof complexity, an area which looks to uncover the limitations of proof systems. In this thesis we investigate the rank complexity of tautologies for several of the most important proof systems based on integer linear programming methods. The three main contributions of this thesis are as follows: Firstly we develop the first rank lower bounds for the proof system based on the Sherali-Adams operator and show that both the Pigeonhole and Least Number Principles require linear rank in this system. We also demonstrate a link between the complexity measures of Sherali-Adams rank and Resolution width. Secondly we present a novel method for deriving rank lower bounds in the well-studied Cutting Planes proof system. We use this technique to show that the Cutting Plane rank of the Pigeonhole Principle is logarithmic. Finally we separate the complexity measures of Resolution width and Sherali-Adams rank from the complexity measures of Lovasz and Schrijver rank and Cutting Planes rank."],"dc:format":["text"],"dc:identifier.uri":["https://etheses.durham.ac.uk/id/eprint/191/1/thesis_mark.pdf"],"dc:publisher.department":["Engineering and Computing Science, School of (2008-2017)"],"dc:publisher.institution":["Durham University"],"dc:relation.isreferencedby":["https://etheses.durham.ac.uk/id/eprint/191/"],"dc:title":["Rank Lower Bounds in Propositional Proof Systems Based on Integer Linear Programming Methods"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["doctoral"],"dc:type.qualificationname":["PhD"]},"updated_at":"2026-07-24T02:11:04Z"}