Stochastic Local Search in k-Term DNF Learning

Proceedings of the Twentieth International Conference on Machine Learning

Volume

Proceedings of the Twentieth International Conference on Machine Learning

Contents

A novel native stochastic local search algorithm for solving k-term DNF problems is presented. It is evaluated on hard k-term DNF problems that lie on the phase transition and compared to the performance of GSAT and WalkSAT type algorithms on SAT encodings of k-term DNF problems. We also evaluate state-of-the-art separate and conquer algorithms on these problems. Finally, we demonstrate the practical relevance of our algorithm on a chess endgame database.