In 1988, Finnish computer scientists Esko Ukkonen and Jorma Tarhio conjectured that the simple greedy algorithm for shortest common superstring has a worst-case approximation ratio of 2. Amazingly, the problem is still open almost 40 years later, despite substantial efforts and partial results by many authors (see e.g. https://arxiv.org/abs/2407.20422v1 for a survey of what is […]
Category: AI
Thoughts on FrontierMath
FrontierMath is the current end boss of math problems for AI. The problems are organized into four tiers. Tier 1 is supposed to be roughly equivalent to international mathematics olympiad problems (i.e. really hard, can take hours to solve or sometimes stump even the very top young math talent), and tier 4 is supposed to […]