[Proof Complexity] Call for presentation of 'International Workshop on Graph Structure and Satisfiability Testing' colocated with SAT 2016

[Massimo Lauria]

Call for presentations
*******************************************************************************
International Workshop on Graph Structure and Satisfiability Testing

colocated with the 19th International Conference on Theory and Applications of
Satisfiability Testing (SAT 2016).

*******************************************************************************

OVERVIEW

A well-established way of describing the structure of SAT instances is to
consider different graphs or hypergraphs that encode the interaction of the
variables in CNF formulas. These graph structures have seen interest in the
last few years both from theory and practice of SAT solving. For example, many
tractable classes of SAT and related problems are characterized by
restrictions of the underlying graph or hypergraph structure whereas lower
bounds in proof complexity and knowledge compilation often use graphs that in a
certain well-defined sense lack this structure. On the more practical side, it
has been shown that good performance of CDCL solvers on practical SAT
instances is related to the community structure of the underlying graphs.
Moreover, graphs play a crucial role in some successful variable choice
heuristics. Yet another connection between SAT and graph theory is the
increasing use of SAT solvers in combinatorial problems, for instance in Ramsey
theory.

The goal of the International Workshop on Graph Structure and Satisfiability
Testing is to bring together researchers from different areas in which there is
an interaction between graph structure and problems related to propositional
satisfiability. The aim is to foster exchange between these areas by presenting
different perspectives, results and current challenges.

The workshop will feature one 50-minute invited talk and several short
contributed talks highlighting different perspectives.


CALL

We solicit contributions in the form of 1-2-page extended abstracts concerned
with all aspects of current research that relates graphs and SAT, interpreted
in a broad sense. Since there will be no proceedings, we explicitly solicit
the submission of talk abstracts describing already published work and work in
progress which falls into the scope of our workshop.

The topics of interest include (but are not limited to) the following:

    SAT algorithms based on graph structure
    Model counting
    Knowledge compilation
    Proof complexity
    Practical evaluation of graph based algorithms
    Variable choice heuristics
    Propagation algorithms
    Analysis and visualization of the structure of practical instances
    Applications of SAT-based techniques to combinatorial problems

Authors of accepted abstracts are expected to give a talk at the workshop.

*******************************************************************************

Invited Speaker

    Stefan Szeider (TU Wien)


Important Dates

    April, 29th, 2016: Submission
    June, 1st, 2016: Notification
    July, 4th, 2016: Workshop


Program Committee

    Gilles Audemard, CRIL, Université d'Artois
    Simone Bova, TU Wien (organizer)
    Massimo Lauria, Universitat Politecnica de Catalunya
    Stefan Mengel, CNRS, CRIL (organizer)
    Igor Razgon, Birkbeck, University of London


Additional information

    https://www.ac.tuwien.ac.at/structsat2016/