ABOUT

The International Conference on Theory and Applications of Satisfiability Testing (SAT) is the premier annual meeting for researchers focusing on the theory and applications of the propositional satisfiability problem, broadly construed. Aside from plain propositional satisfiability, the scope of the meeting 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 tackled using SAT-based techniques, including problems that arise in Formal Verification, Artificial Intelligence, Operations Research, Computational Biology, Cryptology, Data Mining, Machine Learning, Mathematics, et cetera. Indeed, the theoretical and practical advances in SAT research over the past twenty years have contributed to making SAT technology an indispensable tool in a variety of domains.
SAT 2016 invites scientific contributions addressing different aspects of SAT interpreted in a broad sense, including (but not restricted to) theoretical advances (including exact algorithms, proof complexity, and other complexity issues), practical search algorithms, knowledge compilation, implementation-level details of SAT solvers and SAT-based systems, problem encodings and reformulations, applications (including both novel applications domains and improvements to existing approaches), as well as case studies and reports on findings based on rigorous experimentation.
SAT 2016 is organized at the computer science laboratory of The University of Bordeaux under the auspices of SAT Association.

Invited talks

Phokion G. Kolaitis
Coping with Inconsistent Databases: Semantics, Algorithms, and Complexity

(slides of the talk)

Abstract: Managing inconsistency in databases is a long-standing challenge. The framework of database repairs provides a principled approach towards coping with inconsistency in databases. Intuitively, a repair of an inconsistent database is a consistent database that differs from the given inconsistent database in a minimal way. Repair checking and consistent query answering are two fundamental algorithmic problems arising in this context. The first of these two problems asks whether, given two databases, one is a repair of the other. The second asks whether, a query is true on every repair of a given inconsistent database. The aim of this talk is to give an overview of a body of results in this area with emphasis on the computational complexity of repair checking and consistent query answering, including the quest for dichotomy theorems. In addition to presenting open problems, the last part of the talk will include a discussion of the potential use of solvers in developing practical systems for consistent query answering.

About the author: Phokion G. Kolaitis is a Distinguished Professor of Computer Science at the University of California Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity. Kolaitis is a Fellow of the American Association for the Advancement of Science and a Fellow of the Association for Computing Machinery. He is also a co-winner of both the 2008 and the 2014 ACM PODS Alberto O. Mendelzon Test-of-Time Award, and a co-winner of the 2013 International Conference on Database Theory Test-of-Time Award.

David Monniaux
Satisfiability Testing, a Disruptive Technology in Program Verification

Abstract: In the 2000s, progress in satisfiability testing shook automated and assisted program verification. The advent of efficient satisfiability modulo theory (SMT) solvers allowed new approaches: efficient testing and symbolic execution, new methods for generating inductive invariants, and more automated assisted proof. This talk will focus on those new approaches and present some challenges for SAT in program verification.

About the author: David Monniaux is senior researcher (*directeur de recherche*) at the French national scientific research center (CNRS). He works at VERIMAG, a computer science laboratory jointly operated by CNRS and the University of Grenoble. The practical focus of his research is how to prove software correct. This is connected to computability theory, since software correctness, in general, is an undecidable problem, to complexity theory, since many verification problems have high complexity, to mathematical logic, and to fields as diverse as game theory, algebra, and convex optimization. He has been interested, in particular, in proving strong properties of critical software used in civil aviation (e.g. with respect to numerical overflows and floating-point computations). I've also worked on cryptographic protocols and probabilistic systems.

Tosten Schaub (EurAI sponsored)
From SAT to ASP and back!?

(slides of the talk)

Abstract: Answer Set Programming (ASP) provides an approach to declarative problem solving that combines a rich yet simple modeling language with effective Boolean constraint solving capacities. This makes ASP a model, ground, and solve paradigm, in which a problem is expressed as a set of first-order rules, which are subsequently turned into a propositional format by systematically replacing all variables, before finally the models of the resulting propositional rules are computed. ASP is particularly suited for modeling problems in the area of Knowledge Representation and Reasoning involving incomplete, inconsistent, and changing information due to its nonmonotonic semantic foundations. As such, it offers, in addition to satisfiability testing, various reasoning modes, including different forms of model enumeration, intersection or unioning, as well as multi-objective optimization. From a formal perspective, ASP allows for solving all search problems in NP (and NPNP) in a uniform way, that is, by separat- ing problem encodings and instances. Hence, ASP is well-suited for solving hard combinatorial search (and optimization) problems. Interesting applications of ASP include decision support systems for NASA shuttle controllers, industrial team-building, music composition, natural language processing, package configuration, phylogeneticics, robotics, systems biology, timetabling, and many more. The versatility of ASP is nicely reflected by the ASP solver clasp, winning first places at various solver competitions, including ASP, MISC, PB, and SAT. In fact, clasp is at the heart of the open source platform potassco.sourceforge.net. Potassco stands for the “Potsdam Answer Set Solving Collection” and has seen more than 145000 downloads world-wide since its inception at the end of 2008. The talk will start with a gentle introduction to ASP, while focusing on the commonalities and differences to SAT. It will discuss the different semantic foundations and describe the impact of a modelling language along with off- the-shelf grounding systems. Finally, it will highlight some resulting techniques, like meta-programming, preference handling, heuristic constructs, and theory reasoning.

About the author: Torsten Schaub received his diploma and dissertation in informatics in 1990 and 1992, respectively, from the Technical University of Darmstadt, Germany, and his habilitation in informatics in 1995 from the University of Rennes I, France. From 1990 to 1993 he was a research assistant at the Technical University at Darmstadt. From 1993 to 1995, he was a research associate at IRISA/INRIA at Rennes. In 1995 he became University Professor at the University of Angers. Since 1997, he is University Professor for knowledge processing and information systems at the University of Potsdam. In 1999, he became Adjunct Professor at the School of Computing Science at Simon Fraser University, Canada; and since 2006 he is also an Adjunct Professor in the Institute for Integrated and Intelligent Systems at Griffith University, Australia. Since 2014, Torsten Schaub holds an Inria International Chair at Inria Rennes - Bretagne Atlantique. Torsten Schaub has become a fellow of ECCAI in 2012. In 2014 he was elected President of the Association of Logic Programming. He served as program (co-)chair of LPNMR'09, ICLP'10, and ECAI'14. The research interests of Torsten Schaub range from the theoretic foundations to the practical implementation of reasoning from incomplete, inconsistent, and evolving information. His current research focus lies on Answer set programming and materializes at potassco.sourceforge.net, the home of the open source project Potassco bundling software for Answer Set Programming developed at the University of Potsdam.

Call for Papers

The International Conference on Theory and Applications of Satisfiability Testing (SAT) is the premier annual meeting for researchers focusing on the theory and applications of the propositional satisfiability problem, broadly construed. In addition to plain propositional satisfiability, it also includes Boolean optimization (such as 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 tackled using SAT-based techniques including problems that arise in Formal Verification, Artificial Intelligence, Operations Research, Computational Biology, Cryptography, Data Mining, Machine Learning, Mathematics, et cetera. Indeed, the theoretical and practical advances in SAT research over the past twenty years have contributed to making SAT technology an indispensable tool in a variety of domains.

SAT 2016 aims to further advance the field by soliciting original theoretical and practical contributions in these areas with a clear connection to Satisfiability. Specifically, SAT 2016 invites scientific contributions addressing different aspects of SAT interpreted in a broad sense, including (but not restricted to) theoretical advances (such as exact algorithms, proof complexity, and other complexity issues), practical search algorithms, knowledge compilation, implementation-level details of SAT solvers and SAT-based systems, problem encodings and reformulations, applications (including both novel application domains and improvements to existing approaches), as well as case studies and reports on findings based on rigorous experimentation.

SAT 2016 takes place in the nice city of Bordeaux, which is located in the South West of France. Bordeaux is well-known to be the world wine capital, and also ranked UNESCO town.

Follow http://sat2016.labri.fr/, http://twitter.com/sat2016bordeaux or http://www.facebook.com/sat2016bordeaux/ for updates.

SCOPE

SAT 2016 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), as well as 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, see http://www.claymath.org/millennium-problems), 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.

Paper Categories

Submissions to SAT 2016 are solicited in three paper categories, describing original contributions.

• LONG PAPERS (9 to 15 pages, excluding references)
• SHORT PAPERS (up to 8 pages, excluding references)
• TOOL PAPERS (up to 6 pages, excluding references)

LONG and SHORT 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. LONG papers and SHORT papers will be evaluated with the same quality standards, and are expected to contain a similar contribution per page ratio.

The authors should choose between a LONG or a SHORT paper depending on the space they need to fully describe their contribution. The classification between LONG and SHORT papers is mainly a way to balance the workload of the reviewing process among PC members. It also impacts the duration of the presentation of the work during the conference. It is the responsibility of the authors to make sure that their paper is self-contained in the chosen limit of pages. There will be no requalification of the submissions by the PC.

TOOLS papers must obey to a specific content criteria in addition to their size limit. 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. 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.

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

Submissions not consistent with the above guidelines may be returned without review.

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 a supplement when it will help reviewers evaluate the paper. Supplements 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 itself should be self-contained.

Long and short papers may be considered for a best paper award. If the main author is a student, both in terms of work and writing, the paper may be considered for a best student-paper award. Use the supplement to your submission to state (in a brief cover letter) if the paper qualifies as a student paper.

Links to information on the Springer LNCS style are available through the SAT 2016 website at http://sat2016.labri.fr/.

All papers submissions are done exclusively via EasyChair at http://www.easychair.org/conferences/?conf=sat2016.

One author of each accepted paper is expected to present it at the conference.

PROCEEDINGS

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

STUDENT GRANTS

A limited number of student travel support grants will be available from our sponsors. Applicants should acquire a letter of support from their advisor and prepare a statement detailing why the travel support is needed. This information should be emailed to the SAT'16 conference chairs at sat2016@easychair.org by March 31st, 2015. Determinations will be made shortly after the notification to the authors.

ORGANIZATION

PROGRAM CHAIRS

• Nadia Creignou Aix-Marseille Université, France
• Daniel Le Berre Université d'Artois, France

LOCAL CHAIR

• Laurent Simon Université de Bordeaux, France

PROGRAM COMMITTEE

• Fahiem Bacchus University of Toronto
• Yael Ben-Haim IBM Research
• Olaf Beyersdorff University of Leeds
• Armin Biere Johannes Kepler University
• Nikolaj Bjorner Microsoft Research
• Maria Luisa Bonet Universitat Politecnica de Catalunya
• Sam Buss UCSD
• Nadia Creignou Aix-Marseille Université, CNRS
• Uwe Egly TU Wien
• John Franco University of Cincinnati
• Djamal Habet Aix-Marseille Université, CNRS
• Marijn Heule The University of Texas at Austin
• Holger Hoos University of British Columbia
• Frank Hutter University of Freiburg
• Mikolas Janota Microsoft Research
• Matti Järvisalo University of Helsinki
• Hans Kleine Büning University of Paderborn
• Daniel Le Berre Université d'Artois, CNRS
• Ines Lynce INESC-ID/IST, University of Lisbon
• Marco Maratea DIBRIS, University of Genova
• Joao Marques-Silva INESC-ID, IST, ULisbon
• Stefan Mengel CNRS
• Alexander Nadel Intel
• Nina Narodytska Samsung Research America
  
• Jakob Nordström KTH
• Albert Oliveras Technical University of Catalonia
• Roberto Sebastiani DISI, University of Trento
• Martina Seidl Johannes Kepler University Linz
• Yuping Shen Institute of Logic and Cognition, Sun Yat-sen University
• Laurent Simon Bordeaux INP, University of Bordeaux, LaBRI-CNRS
• Takehide Soh Information Science and Technology Center, Kobe University
• Stefan Szeider TU Wien
• Allen Van Gelder University of California, Santa Cruz

CONTACT

sat2016@easychair.org