@inproceedings{BelovJarvisaloStachniak:IJCAI2011, author = {Anton Belov and Matti J\"arvisalo and Zbigniew Stachniak}, title = {Depth-Driven Circuit-Level Stochastic Local Search for {SAT}}, booktitle = {Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011)}, editor = {Toby Walsh}, pages = {504--509}, publisher = {AAAI Press}, year = {2011}, } Abstract: We develop a novel circuit-level stochastic local search (SLS) method D-CRSat for Boolean satisfiability by integrating a structure-based heuristic into the recent CRSat algorithm. D-CRSat significantly improves on CRSat on real-world application benchmarks on which other current CNF and circuit-level SLS methods tend to perform weakly. We also give an intricate proof of probabilistically approximate completeness for D-CRSat, highlighting key features of the method.