Towards a Comprehensive Study of Structural SAT Metrics
Speaker:
Ed Zulkoski, University of Waterloo
Date and Time:
Monday, August 15, 2016 - 3:30pm to 4:30pm
Location:
Bahen Building, Room 1200
Abstract:
Many metrics such as backdoors, community structure, and treewidth have been proposed in an attempt to understand why SAT solvers can solve large industrial instances so quickly. Previous work has studied these metrics in isolation and often using incomparable benchmarks, making comparisons between such metrics difficult. This talk presents preliminary work toward unifying these studies into a single corpus, allowing one to make stronger conclusions regarding the explanatory power of such metrics. We also introduce a new type of backdoors, called LSR backdoors, that extends learning sensitive backdoors to include restarts. We discuss potential practical implications of LSR backdoors in the context of incremental instances.