PC 2018 Home Page


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
Abstract submission deadline   
May 1, 2018
Notification of authors   May 15, 2018 
Workshop dates July 7-8, 2018



The program committee of PC 2018 is shown below. 

Organising Committee

  • Olaf Beyersdorff (Friedrich-Schiller-Universität Jena)
  • Leroy Chew (University of Leeds)
  • Jan Johannsen (Ludwig-Maximilians-Universität München)


The workshop is partly funded by EPSRC (Doctoral Prize Fellowship of Leroy Chew).