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.
Invited Speakers
- Albert Atserias (UPC Barcelona)
- Jakob Nordström (KTH Royal Institute of Technology)
- Pavel Pudlák (Czech Academy of Sciences)
- Iddo Tzameret (Tsinghua University)
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 format via EasyChair:
https://www.easychair.org/conferences/?conf=pc2014
Accepted presentations must be presented at the workshop by one of the authors.
Important Dates
Abstract submission deadline | May 16, 2014 |
Notification of authors | June 2, 2014 |
Workshop dates | July 12-13, 2014 |
Student/Postdoc travel bursaries available
A few bursaries for travel support will be available for students or recent postdocs, who want to attend the workshop. Preference will be given to participants who present a paper at the workshop. Each bursary is worth approx. 400 EUR.
If you are interested, please send an email containing details about your affiliation and submission (if applicable) to Olaf Beyersdorff (o.beyersdorff at leeds.ac.uk). Submissions must be made via EasyChair.
Organization
The program committee of Proof Complexity 2014 is shown below.
- Arnold Beckmann (Swansea University)
- Eli Ben-Sasson (Technion, Haifa)
- Olaf Beyersdorff (University of Leeds) - chair
- Jan Johannsen (LMU Munich) - chair
- Massimo Lauria (KTH Royal Institute of Technology, Stockholm)