Overview
Proof complexity focuses on the complexity of theorem proving procedures. The central question in proof complexity is: given a theorem F (e.g., a propositional tautology) and a proof system P (i.e., a formalism usually comprised of axioms and rules), what is the size of the smallest proof of F in the system P? Moreover, how difficult is it to construct a small proof? Many ingenious techniques have been developed to try to answer these questions; and they bare tight relations to intricate theoretical questions from computational complexity (such as the celebrated P vs. NP problem), first-order arithmetic theories (e.g. separating theories of bounded arithmetic) as well as to practical problems in SAT solving.
The workshop is part of the Federated Logic Conference 2018 in Oxford, UK, affiliated with the SAT conference. There will be a joint session with the Workshop on Quantified Boolean Formulas and Beyond.
Invited Speakers
- Christoph Berkholz (Humboldt Universität zu Berlin)
- Samuel R. Buss (University of California, San Diego)
- Nicola Galesi (Sapienza Universita, Rome)
- Meena Mahajan (IMSc Chennai)
Call for Presentations
We welcome abstracts of 1-2 pages presented finished, ongoing or (if clearly stated) even recently published work on proof complexity. Particular topics of interest are:
- Proof Complexity
- Bounded Arithmetic
- Relations to SAT solving
- Relations to Computational Complexity
Submission Guidelines
Abstracts are invited of ongoing, finished, or (if clearly stated) even recently published work on a topic relevant to the workshop. The abstracts will appear in electronic pre-proceedings that will be distributed at the meeting. Abstracts (at most 2 pages, in LNCS style) are to be submitted electronically in PDF via EasyChair.
Accepted communications must be presented at the workshop by one of the authors.
Important Dates
| Call for papers announced | February 15, 2018 | |
|
May 1, 2018 | |
| Notification of authors | May 15, 2018 | |
| Workshop dates | July 7-8, 2018 |
Organisation
The program committee of PC 2018 is shown below.
- Olaf Beyersdorff (Friedrich Schiller University Jena) - chair
- Ilario Bonacina (UPC Universitat Politecnica de Catalunya)
- Leroy Chew (University of Leeds)
- Yuval Filmus (Technion – Israel Institute of Technology)
- Jan Johannsen (Ludwig Maximilian University of Munich) - chair
- Martina Seidl (Johannes Kepler University Linz)
Organising Committee
- Olaf Beyersdorff (Friedrich-Schiller-Universität Jena)
- Leroy Chew (University of Leeds)
- Jan Johannsen (Ludwig-Maximilians-Universität München)
Acknowledgements
The workshop is partly funded by EPSRC (Doctoral Prize Fellowship of Leroy Chew).