Finding counterexamples to conjectures via reinforcement learning

Adam Wagner
Worcester Polytechnic Institute

In this talk we will leverage a reinforcement learning method, specifically the cross-entropy method, to search for counterexamples to several conjectures in graph theory and combinatorics. We will present a very simplistic setup, in which only minimal changes need to be made (namely the reward function used for RL) in order to successfully attack a wide variety of problems. As a result we will resolve several open problems, and find more elegant counterexamples to previously disproved ones.

Presentation (PDF File)

Back to Machine Assisted Proofs