- Technical Program
- Workshops & Tutorials
- At a glance
- Doctoral Consortium
- Opening & Reception
- Best Papers from Sister Conferences Track
- IJCAI Video Track
- Trading Agent Competion (TAC)
- IJCAI-11 Awards
- Funding Opportunities for International Research Collaborations
- General Game Playing Competition
- Banquet
- Ramon Llull Session
- Industry Day
- Closing Event
- List of Accepted Papers
- Poster Boards
Depth-Driven Circuit-Level Stochastic Local Search for SAT
Anton Belov, Matti Järvisalo and Zbigniew Stachniak
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. In some cases D-CRSat compares favourably even with a modern circuit-level conflict-driven clause learning solver. We also give an intricate proof of probabilistically approximate completeness for D-CRSat, highlighting key features of the method.