Edward Zulkoski
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Edward Zulkoski has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
Krzysztof Czarnecki
University of Waterloo
3 shared publicationsRuben Martins
Carnegie Mellon University
3 shared publicationsVijay Ganesh
University of Waterloo
3 shared publicationsJia Hui Liang
University of Waterloo
2 shared publicationsRobert Robere
University of Toronto
2 shared publicationsChristoph M. Wintersteiger
Microsoft Research
1 shared publication
Latest Publications
- 23 August 2018
- Published by Springer Nature
- p. 436-452
The Effect of Structural Measures and Merges on SAT Solver Performance
- 23 August 2018
- Published by Springer Nature
- p. 436-452
The Effect of Structural Measures and Merges on SAT Solver Performance
- Open Access
Relating Complexity-theoretic Parameters with SAT Solver Performance
Over the years complexity theorists have proposed many structural parameters to explain the surprising efficiency of conflict-driven clause-learning (CDCL) SAT solvers on a wide variety of large industrial Boolean instances. While some of these parameters have been studied empirically, until now there has not been a unified comparative study of their explanatory power on a comprehensive benchmark. We correct this state of affairs by conducting a large-scale empirical evaluation of CDCL SAT solver performance on nearly 7000 industrial and crafted formulas against several structural parameters such as backdoors, treewidth, backbones, and community structure. Our study led us to several results. First, we show that while such parameters only weakly correlate with CDCL solving time, certain combinations of them yield much better regression models. Second, we show how some parameters can be used as a "lens" to better understand the efficiency of different solving heuristics. Finally, we propose a new complexity-theoretic parameter, which we call learning-sensitive with restarts (LSR) backdoors, that extends the notion of learning-sensitive (LS) backdoors to incorporate restarts and discuss algorithms to compute them. We mathematically prove that for certain class of instances minimal LSR-backdoors are exponentially smaller than minimal-LS backdoors.
Open AccessRelating Complexity-theoretic Parameters with SAT Solver Performance
Over the years complexity theorists have proposed many structural parameters to explain the surprising efficiency of conflict-driven clause-learning (CDCL) SAT solvers on a wide variety of large industrial Boolean instances. While some of these parameters have been studied empirically, until now there has not been a unified comparative study of their explanatory power on a comprehensive benchmark. We correct this state of affairs by conducting a large-scale empirical evaluation of CDCL SAT solver performance on nearly 7000 industrial and crafted formulas against several structural parameters such as backdoors, treewidth, backbones, and community structure. Our study led us to several results. First, we show that while such parameters only weakly correlate with CDCL solving time, certain combinations of them yield much better regression models. Second, we show how some parameters can be used as a "lens" to better understand the efficiency of different solving heuristics. Finally, we propose a new complexity-theoretic parameter, which we call learning-sensitive with restarts (LSR) backdoors, that extends the notion of learning-sensitive (LS) backdoors to incorporate restarts and discuss algorithms to compute them. We mathematically prove that for certain class of instances minimal LSR-backdoors are exponentially smaller than minimal-LS backdoors.