[Proof Complexity] Deadline extended: FLoC Proof Complexity Workshop

Marc Vinyals vinyals at kth.se
Tue May 17 23:04:23 CEST 2022

Dear colleagues,

The deadline for submitting abstracts to the FLoC worskhop on proof
complexity has been extended to June 1st. The workshop itself will take
place during July 31st - August 1st in Haifa, just before SAT and LICS,
as part of FLoC. Travel support for students is available in exchange
for volunteer work at the (FLoC) conference, see

An updated call for presentations follows.


FLoC workshop on proof complexity - Call for Presentations

Haifa, 31 July -- 1 August 2022

The workshop will be part of FLoC and will be affiliated with the
conference SAT'22.

=== Important Dates ===

 1 June 2022 ................... Abstract submission
15 June 2022 ................... Notification to authors
31 July -- 1 August 2022 ....... Workshop in Haifa

=== Format ===

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

=== 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

 *  Proof Complexity
 *  Bounded Arithmetic
 *  Relations to SAT/QBF 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; references do not count
towards the limit) are to be submitted electronically in PDF via


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

=== Program Committee ===

 * Olaf Beyersdorff (Friedrich-Schiller-Universität Jena)
 * Susanna de Rezende (Lund University)
 * Jan Johannsen (Ludwig-Maximilians-Universität München)
 * Ján Pich (University of Oxford)
 * Robert Robere (McGill University)
 * Friedrich Slivovsky (TU Vienna)
 * Marc Vinyals

=== Organizers ===

 * Olaf Beyersdorff (Friedrich-Schiller-Universität Jena)
 * Jan Johannsen (Ludwig-Maximilians-Universität München)
 * Marc Vinyals

More information about the Proof-Complexity mailing list