31 July - 1 August 2022, FLoC Workshop on Proof Complexity, Haifa, Israel
Proof complexity is the study of 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, 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 conference SAT'22.
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 * Relations to Computational Complexity. 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.