7. SAT 2004: Vancouver, BC, Canada

SAT 2004 - The Seventh International Conference on Theory and Applications of Satisfiability Testing, 10-13 May 2004, Vancouver, BC, Canada, Online Proceedings. 2004 BibTeX

Hard instances

Harold S. Connamacher:
A Random Constraint Satisfaction Problem That Seems Hard for DPLL.
Electronic Edition (link) BibTeX
Haixia Jia, Cristopher Moore, Bart Selman:
From Spin Glasses to Hard Satisfiable Formulas.
Electronic Edition (link) BibTeX

SAT Solvers

Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi:
Combining Component Caching and Clause Learning for Effective Model Counting.
Electronic Edition (link) BibTeX
Matthew D. T. Lewis, Tobias Schubert, Bernd Becker:
Early Conflict Detection Based BCP for SAT Solving.
Electronic Edition (link) BibTeX
Dave A. D. Tompkins, Holger H. Hoos:
UBCSAT: An Implementation and Experimentation Environment for SLS Algorithms for SAT & MAX-SAT.
Electronic Edition (link) BibTeX
HoonSang Jin, Fabio Somenzi:
CirCUs: A Hybrid Satisfiability Solver.
Electronic Edition (link) BibTeX

Algorithms & Bounds I

Shlomo Hoory, Stefan Szeider:
Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable.
Electronic Edition (link) BibTeX
Ravi Gummadi, N. S. Narayanaswamy, Venkatakrishnan Ramaswamy:
Algorithms for Satisfiability using Independent Sets of Variables.
Electronic Edition (link) BibTeX

SAT Solvers Competition & QBF Solvers Evaluation

Algorithms & Bounds II

Evgeny Dantsin, Alexander Wolpert:
Derandomization of Schuler's Algorithm for SAT.
Electronic Edition (link) BibTeX
Nicola Galesi, Oliver Kullmann:
Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank.
Electronic Edition (link) BibTeX
Yannet Interian:
Approximation Algorithm for Random MAX-kSAT.
Electronic Edition (link) BibTeX

Properties of Formulae / Non-Boolean Problems

Naomi Nishimura, Prabhakar Ragde, Stefan Szeider:
Detecting Backdoor Sets with Respect to Horn and Binary Clauses.
Electronic Edition (link) BibTeX
Zbigniew Stachniak:
A Note on Satisfying Truth-Value Assignments of Boolean Formulas.
Electronic Edition (link) BibTeX
Carlos Ansótegui, Felip Manyà:
Mapping Problems with Finite-Domain Variables into Problems with Boolean Variables.
Electronic Edition (link) BibTeX
Vasco M. Manquinho, João P. Marques Silva:
Using Lower-Bound Estimates in SAT-Based Pseudo-Boolean Optimization.
Electronic Edition (link) BibTeX

Poster Overview Session I

Stefan Porschen, Ewald Speckenmeyer:
Worst Case Bounds for some NP-Complete Modified Horn-SAT Problems.
Electronic Edition (link) BibTeX
Danila A. Sinopalnikov:
Satisfiability Threshold of the Skewed Random k-SAT.
Electronic Edition (link) BibTeX
Steven David Prestwich, Colin Quirke:
Local Search for Very Large SAT Problems.
Electronic Edition (link) BibTeX
Lengning Liu, Miroslaw Truszczynski:
Local Search with Bootstrapping.
Electronic Edition (link) BibTeX
Alex S. Fukunaga:
Efficient Implementations of SAT Local Search.
Electronic Edition (link) BibTeX
Renato Bruni, Andrea Santori:
Adding a New Conflict Based Branching Heuristic in two Evolved DPLL SAT Solvers.
Electronic Edition (link) BibTeX
Elsa Carvalho, João P. Marques Silva:
Using Rewarding Mechanisms for Improving Branching Heuristics.
Electronic Edition (link) BibTeX
Inês Lynce, João P. Marques Silva:
On Computing Minimum Unsatisfiable Cores.
Electronic Edition (link) BibTeX
Carsten Sinz:
Visualizing the Internal Structure of SAT Instances (Preliminary Report).
Electronic Edition (link) BibTeX

Non-CNF SAT I

Jinbo Huang, Adnan Darwiche:
Using DPLL for Efficient OBDD Construction.
Electronic Edition (link) BibTeX
Guoqiang Pan, Moshe Y. Vardi:
Search vs. Symbolic Techniques in Satisfiability Solving.
Electronic Edition (link) BibTeX
Christian Thiffault, Fahiem Bacchus, Toby Walsh:
Solving Non-clausal Formulas with DPLL search.
Electronic Edition (link) BibTeX
Éric Grégoire, Richard Ostrowski, Bertrand Mazure, Lakhdar Sais:
Automatic Extraction of Functional Dependencies.
Electronic Edition (link) BibTeX

Non-CNF SAT II

Alessandro Armando, Claudio Castellini, Enrico Giunchiglia, Marco Maratea:
A SAT-based Decision Procedure for the Boolean Combination of Difference Constraints.
Electronic Edition (link) BibTeX
Marijn Heule, Hans van Maaren:
Aligning CNF- and Equivalence-reasoning.
Electronic Edition (link) BibTeX
Michael Bauland, Philippe Chapdelaine, Nadia Creignou, Miki Hermann, Heribert Vollmer:
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries.
Electronic Edition (link) BibTeX
Hantao Zhang, Dapeng Li, Haiou Shen:
A SAT Based Scheduler for Tournament Schedules.
Electronic Edition (link) BibTeX

Bounded Model Checking

Marco Benedetti, Sara Bernardini:
Incremental Compilation-to-SAT Procedures.
Electronic Edition (link) BibTeX
Daijue Tang, Yinlei Yu, Darsh Ranjan, Sharad Malik:
Analysis of Search Based Algorithms for Satisfiability of Quantified Boolean Formulas Arising from Circuit State Space Diameter Problems.
Electronic Edition (link) BibTeX

QBF

Hubie Chen, Víctor Dalmau:
Looking Algebraically at Tractable Quantified Boolean Formulas.
Electronic Edition (link) BibTeX
Hans Kleine Büning, Xishun Zhao:
Equivalence Models for Quantified Boolean Formulas.
Electronic Edition (link) BibTeX
Miroslav N. Velev:
Encoding Global Unobservability for Efficient Translation to SAT.
Electronic Edition (link) BibTeX
Armin Biere:
Resolve and Expand.
Electronic Edition (link) BibTeX
Enrico Giunchiglia, Massimo Narizzano, Armando Tacchella:
QBF Reasoning on Real-World Instances.
Electronic Edition (link) BibTeX

Poster Overview Session II

Darsh P. Ranjan, Daijue Tang, Sharad Malik:
A Comparative Study of 2QBF Algorithms.
Electronic Edition (link) BibTeX
Gilles Audemard, Bertrand Mazure, Lakhdar Sais:
Dealing with Symmetries in Quantified Boolean Formulas.
Electronic Edition (link) BibTeX
Zhuo Huang, Hantao Zhang, Jian Zhang:
Improving First-order Model Searching by Propositional Reasoning and Lemma Learning.
Electronic Edition (link) BibTeX
Nachum Dershowitz, Jieh Hsiang, Guan-Shieng Huang, Daher Kaiss:
Boolean Ring Satisfiability.
Electronic Edition (link) BibTeX
Ling Zhao, Martin Müller:
Game-SAT: A Preliminary Report.
Electronic Edition (link) BibTeX
Carsten Sinz, Wolfgang Küchlin:
Verifying the On-Line Help System of SIEMENS Magnetic Resonance Tomographs using SAT (Extended Abstract).
Electronic Edition (link) BibTeX
Sathiamoorthy Subbarayan, Dhiraj K. Pradhan:
NiVER: Non Increasing Variable Elimination Resolution for Preprocessing SAT instances.
Electronic Edition (link) BibTeX
Daniel Sheridan:
The Optimality of a Fast CNF Conversion and its Use with SAT.
Electronic Edition (link) BibTeX
Olivier Bailleux, Yacine Boufkhad:
Full CNF Encoding: The Counting Constraints Case.
Electronic Edition (link) BibTeX