RL finds counterexamples to open problems in graph theory

Stream: Machine Learning for Theorem Proving

[Johan Commelin]

https://arxiv.org/abs/2104.14516
https://twitter.com/wtgowers/status/1388458562775654401

An interesting paper by Adam Wagner appeared on arXiv a couple of days ago (thanks to Imre Leader for drawing my attention to it), which uses reinforcement learning to find non-trivial counterexamples to several conjectures in graph theory. 1/ https://arxiv.org/pdf/2104.14516.pdf

- Timothy Gowers (@wtgowers)

[Daniel Selsam]

I am curious how important the RL/MLP component actually is in these results. It would be nice to see local-search baselines, i.e. considering local transformations in encoding space that improve the score, rather than nonlinearly warping the space with an MLP.