"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."
Thanks for sharing. Very interesting. Added the formula to my fibonacci number algos collection at https://github.com/alidasdan/fibonacci-number-algorithms . Though simple, the new formula runs much slower than even the linear-time algo.
There are a couple of well-known algorithms to find the best rational approximation to a given real number. A good and short book is "Diophantine Approximations" by I. Niven. For code, you can also check out this repo of mine: https://github.com/alidasdan/best-rational-approximation .
Note that decimal numbers represented as a floating point numbers on a computer are actually rational numbers due to limited precision. So converting decimal numbers to fractions, both stored on a computer, means converting a fraction with potentially large numerator and/or denominator to a simpler fraction, say, one with a far smaller denonimator.
For example, an approximation to pi is 3.14159265358979323844, which is the same thing as 314159265358979323844/10^20 (trivial approximation). Using these algorithms we can covert this fraction to a simpler fraction under different approximation criteria such as a bound on the approximation error or a bound on the magnitude of the denominator. For this example, we then get various approximations to pi such as 22/7, 355/113, ...
Binary decision diagrams (BDDs) have been a big deal in electronic design automation (EDA); many of the BDD developments have happened as a result of the applications in EDA.
For a recent and comprehensive coverage, you can check out D. Knuth's fascicle as part of his well-known book. The BDD fascicle and other fascicles are available at http://www.cs.utsa.edu/~wagner/knuth/ .
Thank you for your feedback. I am one of the authors of this paper.
I don't think the paper gives any hints on us dividing universities into classes and comparing. Would love to know how you reached that conclusion.
At the same time, yes, we could have divided universities into different classes: research vs liberal arts, this vs. that state, big vs. small size, etc. These are all trivial groupings but none of these would change the conclusions of this paper. For all practical purposes, we could easily have replaced the university names with labels like U1, U2, ... and still the conclusions would not change. What matters is how a weight-based composite index can be gamed and the paper does show that in multiple ways. Pls review the ILP formulations yourself and run them on the dataset of your choice.
reply