PatternBoost: Constructions in Mathematics with a Little Help from AI
Preprint
Abstract
We introduce PatternBoost, a flexible method for finding interesting constructions in mathematics. Our algorithm alternates between two phases. In the first ``local'' phase, a classical search algorithm is used to produce many desirable constructions. In the second ``global'' phase, a transformer neural network is trained on the best such constructions. Samples from the trained transformer are then used as seeds for the first phase, and the process is repeated. We give a detailed introduction to this technique, and discuss the results of its application to several problems in extremal combinatorics. The performance of PatternBoost varies across different problems, but there are many situations where its performance is quite impressive. Using our technique, we find the best known solutions to several long-standing problems, including the construction of a counterexample to a conjecture that had remained open for 30 years.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Decomposing the complete r-graphJournal of Combinatorial Theory, Series A, 2018
- A note on the random greedy independent set algorithmRandom Structures & Algorithms, 2016
- Kleitman and combinatoricsDiscrete Mathematics, 2002
- On partitions of discrete boxesDiscrete Mathematics, 2002
- Hypercube subgraphs with minimal detoursJournal of Graph Theory, 1996
- Edge deletion preserving the diameter of the hypercubeDiscrete Applied Mathematics, 1995
- A NEURAL NETWORK BASED APPROACH TO MECHANICAL DESIGN OPTIMIZATIONEngineering Optimization, 1992
- Changing and unchanging the diameter of a hypercubeDiscrete Applied Mathematics, 1992
- Approximation capabilities of multilayer feedforward networksNeural Networks, 1991
- Approximation by superpositions of a sigmoidal functionMathematics of Control, Signals, and Systems, 1989