Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-061 | 29th April 2021 17:40

Reflections on Proof Complexity and Counting Principles

RSS-Feed




TR21-061
Authors: Noah Fleming, Toniann Pitassi
Publication: 29th April 2021 23:10
Downloads: 115
Keywords: 


Abstract:

This paper surveys the development of propositional proof complexity and the seminal contributions of Alasdair Urquhart. We focus on the central role of counting principles, and in particular Tseitin's graph tautologies, to most of the key advances in lower bounds in proof complexity. We reflect on a couple of key ideas that Urquhart pioneered: (i) graph expansion as a tool for distinguishing between easy and hard principles, and (ii) ``reductive" lower bound arguments, proving via a simulation theorem that an optimal proof cannot bypass the obvious (inefficient) one.



ISSN 1433-8092 | Imprint