FLoC Proof Complexity Workshop

Overview

The workshop is part of the Federated Logic Conference 2022 in Haifa, Israel, affiliated with the 25nd International Conference on Theory and Applications of Satisfiability Testing. There will be a joint session with the Workshop on Quantified Boolean Formulas and Beyond.

The topic of the workshop will be on proof complexity in a broad sense, and including proof complexity, bounded arithmetic, relations to SAT solving, relations to computational complexity, etc.

Important Dates

Abstract submission
1 June 2022
Notification to authors
15 June 2022
Workshop dates
July 31 — August 1, 2022

Format

We plan to hold the workshop as an offline-only event.

Program

https://easychair.org/smart-program/FLoC2022/PC-index.html

Scope

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.

Invited Speakers

Submissions

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

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; references do not count towards the limit) are to be submitted electronically in PDF via EasyChair

http://www.easychair.org/conferences/?conf=pc2022

Accepted communications must be presented at the workshop by one of the authors.

Program Committee

Organizers

Previous Editions