MSc thesis defense presentation
Θεόδωρος Παπαμακάριος defends his MSc thesis
|Date:||Τετάρτη, 19 Ιούλ 2017|
|Location:||Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ (παλαιά κτήρια), 1.1.31|
|Thesis title:||Proof Complexity: A Tableau Perspective|
The method of semantic tableaux (or simply tableaux) is arguably one of the most elegant proof systems. Unfortunately, it hasn't received much attention in the proof complexity literature, mainly due to early negative results, concerning the complexity of cut-free tableaux. We bring tableaux to the fore, introducing the measures of tableau depth and width. Equipped with these, we show in an elegant, uniform way several known results spanning proof complexity, from a tableau viewpoint.