SAT 2016

Bordeaux, France,
5th-8th July

  • Registrations and Venue informations are open! (Register Now)
  • Early birds until 27th of may!

19th International Conference on Theory
and Applications of Satisfiability Testing
taking place at the
Computer Science Laboratory of Bordeaux(Labri)
the
5th-8th July, 2016

ORGANIZATION

PROGRAM CHAIRS

Nadia Creignou and Daniel Le Berre

LOCAL ORGANIZATION

Laurent Simon

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.

IMPORTANT DATES

All deadlines are at 23:59 UTC-12 ("anywhere in the world")


Abstract Submission: February, 14th, 2016 February, 21th, 2016 (New)
Paper Submission: February, 21th, 2016
Paper Updates: February, 24th, 2016 (New)
(Papers are due by the 21th but can be updated until the 24th)

Rebuttal: March, 21th-23th, 2016
Notifications: April, 3rd, 2016
Final Versions: April, 23th, 2016

Workshops: July, 4th, 2016
Conference: July, 5th-8th, 2016

Invited talks

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

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 Kolaitis is a Distinguished Professor of Computer Science at UC Santa Cruz and a Principal Research Staff Member of the Computer Science Principles and Methodologies Department (a.k.a. the Theory Group) at the IBM Almaden Research Center. He served as Chair of the Computer Science Department at UC Santa Cruz from July 1997 to June 2001, and then again from July 2014 to June 2015. From June 2004 to September 2008, he served as Senior Manager of the Computer Science Principles and Methodologies Department at the IBM Almaden Research Center (and while on leave of absence from UC Santa Cruz). His research interests include principles of database systems, logic in computer science, and computational complexity.

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!?

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.

Accepted papers

We received 70 submissions this year: 48 long papers, 13 short papers and 9 tool papers. The papers have been reviewed by the program committee (33 members), with the help of 65 additional reviewers. Each submission was reviewed by at least 3 different reviewers. A rebuttal period allowed the authors to provide a feedback to the reviewers. After that, the discussion among the PC took place. The rebuttal played an important role in that phase, since in many cases the rebuttal either confirmed or changed the original recommendation of many reviewers (positively or negatively). The final recommendation has been to accept 31 submissions (22 long, 4 short and 5 tool papers) and to accept conditionally 5 additional papers. This year, the authors received a meta-review, summarizing the discussion which occurred after the rebuttal and the reasons of the final recommendation.

List of accepted papers (without conditional ones)

Florian Lonsing, Uwe Egly and Martina Seidl. Q-Resolution with Generalized Axioms
Mathias Soeken, Alan Mishchenko, Ana Petkovska, Baruch Sterin, Paolo Ienne, Robert Brayton and Giovanni De Micheli. Heuristic NPN classification for large functions using AIGs and LEXSAT
Norbert Manthey and Marius Lindauer. SpyBug: Automated Bug Detection in the Configuration Space of SAT Solvers
Johannes K. Fichte, Arne Meier and Irina Schindler . Strong Backdoors for Default Logic
Patrick Scharpfenecker and Jacobo Torán. Solution-Graphs of Boolean Formulas and Isomorphism
Stefan Mengel. Parameterized Compilation Lower Bounds for Restricted CNF-formulas
Cuong Chau and Marijn Heule. Computing Maximum Unavoidable Subgraphs using SAT Solvers
Neha Lodha, Sebastian Ordyniak and Stefan Szeider . A SAT Approach to Branchwidth
Marijn Heule, Oliver Kullmann and Victor Marek. Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer
Olaf Beyersdorff, Leroy Chew, Renate Schmidt and Martin Suda. Lifting QBF Resolution Calculi to DQBF
Tomáš Peitl, Friedrich Slivovsky and Stefan Szeider. Long Distance Q-Resolution with Dependency Schemes
Paul Saikko, Jeremias Berg and Matti Järvisalo . LMHS: A SAT-IP Hybrid MaxSAT Solver
Martin Jonas and Jan Strejcek. Solving Quantified Bit-Vector Formulas Using Binary Decision Diagrams
Tomas Balyo and Florian Lonsing. HordeQBF: A Modular and Massively Parallel QBF Solver
Jia Liang, Vijay Ganesh, Pascal Poupart and Krzysztof Czarnecki. Learning Rate Based Branching Heuristic for SAT Solvers
Jo Devriendt, Bart Bogaerts, Maurice Bruynooghe and Marc Denecker. Improved static symmetry breaking for SAT
Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordstrom and Marc Vinyals. Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers
Mikolas Janota. On Q-Resolution and DPLL QBF Solving
Zurab Khasidashvili and Konstantin Korovin. Predicate elimination for preprocessing in first-order theorem proving
Jeevana Priya Inala, Rohit Singh and Armando Solar-Lezama. Synthesis of Domain Specific CNF Encoders for Bit-Vector Solvers
Valeriy Balabanov, Jie-Hong Roland Jiang, Alan Mishchenko, Christoph Scholl and Robert K. Brayton. 2QBF: challenges and solutions
Antti Hyvärinen, Matteo Marescotti, Leonardo Alt and Natasha Sharygina. OpenSMT2: An SMT Solver for Multi-Core and Cloud Computing
Lorenzo Candeago, Daniel Larraz, Albert Oliveras, Enric Rodríguez Carbonell and Albert Rubio. Speeding Up the Constraint-Based Method in Difference Logic
Aleksandar Zeljić, Christoph M. Wintersteiger and Philipp Ruemmer. Deciding Bit-Vector Formulas with mcSAT
M. Fareed Arif, Carlos Mencia, Alexey Ignatiev, Norbert Manthey, Rafael Penaloza and Joao Marques-Silva . BEACON: An Efficient SAT-Based Tool for Debugging EL+ Ontologies
Carlos Mencía, Alexey Ignatiev, Alessandro Previti and Joao Marques-Silva. MCS Extraction with Sublinear Oracle Calls
Gilles Audemard and Laurent Simon. Adaptation to Extreme Cases and Specialized Phase for Restarts: New Flavors in the Glucose 2016 Vintage
Giles Reger, Martin Suda and Andrei Voronkov. Finding Finite Models in Multi-Sorted First Order Logic
Uwe Egly. On stronger calculi for QBFs
Leander Tentrup. Non-prenex QBF Solving using Abstraction
Mateus de Oliveira Oliveira. Satisfiability via Smooth Pictures

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

CONTACT / ADDRESS


Laurent Simon

Conference Location

Labri -- Laboratoire Bordelais de Recherche en Informatique
351, cours de la Libération,
Talence, France.