[Proof Complexity] SAT 2013 call for papers --- proof complexity papers welcomed

Jakob Nordstrom jakobn at kth.se
Fri Dec 21 22:32:41 CET 2012

Dear colleagues,

For your information, please find below the call for papers for SAT 2013.

The chairs have asked me to emphasize that proof complexity papers would
be very welcome, especially papers making connections to SAT solving. And
Helsinki is very nice in summer (well, maybe not as nice as Stockholm, but
still nice ;-) ).

With best regards,
Jakob Nordstrom

Jakob Nordström, Assistant Professor
KTH Royal Institute of Technology


[ We apologize if you receive multiple copies of this call. ]

                       1st CALL FOR PAPERS

               Sixteenth International Conference on
                        --- SAT 2013 ---

               Helsinki, Finland, July 8-12, 2013

         Abstract submission deadline: February  1, 2013
            Paper submission deadline: February  8, 2013


The International Conference on Theory and Applications of
Satisfiability Testing (SAT) is the primary annual meeting for
researchers studying the theory and applications of the propositional
satisfiability problem, broadly construed.  Besides plain propositional
satisfiability, it includes Boolean optimization (including MaxSAT and
Pseudo-Boolean (PB) constraints), Quantified Boolean Formulas (QBF),
Satisfiability Modulo Theories (SMT), and Constraint Programming (CP)
for problems with clear connections to Boolean-level reasoning.

Many hard combinatorial problems can be encoded as SAT instances, in the
broad sense mentioned above, including problems in formal verification
(hardware and software), artificial intelligence, and operations research.
More recently, biology, cryptology, data mining, machine learning, and
mathematics have been added to the growing list.

The SAT conference aims to further advance the field by soliciting original
theoretical and practical contributions in these areas with a clear
connection to satisfiability.

SAT 2013 takes place in Helsinki, the capital of Finland. Helsinki is a
vibrant Scandinavian and international city with a lot to offer to visitors.
SAT 2013 takes place during the main summer season, allowing one to
experience the whitenights during which the sun almost never sets.


(Follow http://sat2013.cs.helsinki.fi/ for updates.)

February  1, 2013: Abstract Submission
February  8, 2013: Paper Submission
March    18, 2013 (approx.): Response from Authors begins, lasts 72 hours
April     3, 2013: Acceptance Notifications
April    22, 2013: Final Camera-Ready Versions

July      8, 2013: Workshops begin
July   9-12, 2013: Main Conference


SAT 2013 welcomes scientific contributions addressing different aspects of
the satisfiability problem. interpreted in a broad sense.  Domains include
MaxSAT and Pseudo-Boolean (PB) constraints, Quantified Boolean Formulae
Satisfiability Modulo Theories (SMT), Constraint Satisfaction Problems (CSP).

Topics include (but are not restricted to)

  Theoretical advances (including exact algorithms, proof complexity, and
    other complexity issues);

  Practical search algorithms;

  Knowledge compilation;

  Implementation-level details of SAT solving tools and SAT-based systems;

  Problem encodings and reformulations;

  Applications (including both novel applications domains and
    improvements to existing approaches);

  Case studies and reports on insightful findings based on rigorous


Papers claiming to resolve a major long-standing open theoretical
question in mathematics or computer science (such as those for which a
Millennium Prize is offered, see http://www.claymath.org/millennium)
are outside the scope of the conference because there is insufficient
time in the schedule to referee such papers; instead, such papers
should be submitted to an appropriate technical journal.


Submissions to SAT 2013 are solicited in three paper categories, describing
original contributions:

  REGULAR PAPERS (9 to 15 pages, excluding references)
    Regular papers should contain original research, with sufficient detail
    to assess the merits and relevance of the contribution.
    For papers reporting experimental results, authors are strongly
    to make their data and implementations available with their submission.
    Submissions reporting on case studies are also encouraged, and should
    describe details, weaknesses, and strengths in sufficient depth.

  SHORT PAPERS (up to 8 pages, excluding references)
    The same evaluation criteria apply to short papers as to regular papers.
    They will be reviewed to the same standards of quality as regular papers,
    but will naturally contain less quantity of new material.
    Short papers will have the same status as regular papers and be eligible
    for the same awards (to be announced later).

  TOOL PAPERS (up to 6 pages, excluding references)
    A tool paper should describe the implemented tool and its novel features.
    Here "tools" are interpreted in a broad sense, including descriptions of
    implementations of core SAT solving techniques (solvers, preprocessors,
    etc.), systems exploiting SAT solvers or their extensions for solving
    interesting problem domains, etc.
    A demonstration is expected to accompany a tool presentation.
    Papers describing tools that have already been presented previously are
    expected to contain significant and clear enhancements to the tool.
    The software for the tool should be made publicly available, for
    accepted tool papers, and should at least be available to reviewers
    for evaluation during the review period. Evaluation criteria will include
    (but not be limited to) accurate documentation, usability, and
    potential for furthering the state of the art.  For the latter criterion,
    availability of source code will be a significant factor.
    This is an evolving category, and technical issues involving software
    availability should be discussed with the program chairs.
    Be sure to check the conference web page for updates on this category.
    Papers describing unpublished tool-related work, providing details on a
    system and the novel algorithms it implements, as well as an experimental
    evaluation of the system's performance, can also be submitted as regular

For all paper categories, the page limits stated above do not include
references, but do include all other material intended to appear in the
conference proceedings. An additional technical appendix may be included,
but it must be clearly labeled as supplementary material and may or may
not be examined during review based of the considerations of individual
reviewers. The appendix may contain detailed proofs, examples, descriptions
of publicly available software related to the submission, or other
information  that does not fit the page limit. However, the appendix will
not be included in the conference proceedings. The main contributions
should be made accessible within the page limits, without having to
rely on the appendix.

Submissions should not be under review elsewhere nor be submitted elsewhere
while under review for SAT 2013, and should not consist of previously
published material.

Submissions must use the Springer LNCS style without modifications,
and must be written in English. All papers submissions are done exclusively
via the SAT 2013 EasyChair Conference Service at
http://www.easychair.org/conferences/?conf=sat2013 .


All accepted papers will be published in the proceedings of the conference,
which will be published within the Springer LNCS series.

Matti Jarvisalo        University of Helsinki, Finland
Allen Van Gelder       University of California at Santa Cruz, USA

Gilles Audemard
Fahiem Bacchus
Armin Biere
Maria Luisa Bonet
Lucas Bordeaux
Uwe Bubeck
Samuel Buss
Nadia Creignou
Leonardo de Moura
John Franco
Enrico Giunchiglia
Ziyad Hanna
Marijn Heule
Holger H. Hoos
Jinbo Huang
Tommi Junttila
Matti Jarvisalo
Arist Kojevnikov
Daniel Kroening
Oliver Kullmann
Daniel Le Berre
Florian Lonsing
Ines Lynce
Joao Marques-Silva
Alexander Nadel
Jakob Nordstrom
Albert Oliveras
Ramamohan Paturi
Jussi Rintanen
Olivier Roussel
Ashish Sabharwal
Lakhdar Sais
Roberto Sebastiani
Bart Selman
Peter Stuckey
Stefan Szeider
Naoyuki Tamura
Allen Van Gelder
Toby Walsh

More information about the Proof-Complexity mailing list