Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

7 - 8 July 2018, Workshop on Proof Complexity 2018 (PC 2018), Oxford, England

Date: 7 - 8 July 2018
Location: Oxford, England
Deadline: Sunday 15 April 2018

Proof complexity is the study of the complexity of theorem proving procedures. The central question in proof complexity is: given a theorem F and a proof system P, 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, which bare tight relations to intricate theoretical open problems from computational complexity (such as the celebrated P vs. NP problem), mathematical logic (e.g. separating theories of Bounded Arithmetic) as well as to practical problems in SAT/QBF solving.

The workshop will be part of FLoC and will be affiliated with the conferences SAT'18 and LICS'18.

We welcome 1-2-page abstracts presenting (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/QBF solving, and Relations to Computational Complexity. The abstracts will appear in electronic pre-proceedings that will be distributed at the meeting. Accepted communications must be presented at the workshop by one of the authors.

For more information, see http://easychair.org/smart-program/PC2018/.

Please note that this newsitem has been archived, and may contain outdated information or links.