Imagine a true statement about finite objects, how can a formal proof of such a statement look? Can it be short? This semester's topic will be about basic propositional proof systems studied in proof complexity (namely Resolution, Frege system, and some algebraic and geometric systems). During the seminars, which will be as interactive as possible, we will work on various exercises which will guide us through the feel of proving something in those proof systems. We will also focus on studying classic lower bounds for those systems. In the later parts of the semester, the students will be free to pick a topic to present, but active participation will be enough to obtain the credit (zápočet). No prior knowledge is assumed, everything is to be explained on the seminar.
The program of the past semesters can be found at professor Krajíček's website.
This semester we will unfortunately not be present in Prague for the most of October, so the official program will start in November. The timeslot for the seminar is not neccesarily set in stone and if there is a better time for most participants, can be changed. So either come join us for the first organizational meeting, or please send us your time preferences by email.
Our seminar meets regularly to discuss the assigned readings. Here is the schedule:
If you have any questions or would like to join our seminar, please feel free to contact us: