[Proof Complexity] FLoC Proof Complexity Workshop

Marc Vinyals vinyals at kth.se
Fri Apr 22 13:42:45 CEST 2022

Dear colleagues,

There will be a workshop on proof complexity this summer in Haifa, in
connection with the Federated Logic Conference. Everybody is welcome to
attend and to propose talks, see the announcement below.


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

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

=== 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) are to be submitted
electronically in PDF via EasyChair


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