Call for Papers
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.
See the separate Important Dates page.
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 (QBF), 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 experimentation
Out of Scope
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) 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 (over 8, up 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 encouraged 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 implemented solvers, preprocessors, etc., as well as systems that exploit SAT solvers or their extensions to solve interesting problem domains, etc. A demonstration is expected to accompany a tool presentation, and the software for the tool should be made publicly available. Papers describing tools that have already been presented previously are expected to contain significant and clear enhancements to the tool. Evaluation criteria include (but are not limited to) accurate documentation, usability, and potential for furthering the state of the art, with availability of source code being a significant factor.
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.
Besides the paper itself, authors may submit a supplement consisting of one file in the format of a gzipped tarball (.tar.gz or .tgz) or a gzipped file (.gz) or a zip archive (.zip). Authors are encouraged to submit such a supplement when it will help reviewers to evaluate the paper, and such a supplement will be treated with the same degree of confidentiality as the paper itself. For example, the supplement might contain detailed proofs, examples, software, detailed experimental data, or other material related to the submission. Individual reviewers may or may not consult the supplementary material; the paper should be self-contained.
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 should use the Springer LNCS style (without space-squeezing or other modifications), be written in English, and submitted in PDF format. All papers submissions are done exclusively via the SAT 2013 EasyChair Conference Service at
Submissions not consistent with the above guidelines may be returned without review.
One author of each accepted paper is expected to present it at the conference.
Information on the Springer LNCS style is available at http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0. The latex2e package is at ftp://ftp.springer.de/pub/tex/latex/llncs/latex2e/llncs2e.zip. The copyright form (for accepted papers) is at http://www.springer.com/cda/content/document/cda_downloaddocument/copyrightlncs_17-DEZ-2012.pdf?SGWID=0-0-45-154182-0.
All accepted papers will be published in the proceedings of the conference, which will be published within the Springer Lecture Notes in Computer Science series.