About
Big O Speedrun tracks improved algorithmic bounds for classic problems. Each result links to its source and states the evidence behind it.
How it works
Each problem page gives the precise problem statement, lists results, and shows progress over time. The table combines results from the listed sources. Each result keeps its assumptions and evidence level.
Frequently asked questions
How are problems chosen?
We start with classic problems whose long standing bounds have recently improved. Each problem needs a precise statement and a bound that we can track.
Can I add a problem?
Yes. Suggest it through GitHub. Include the problem statement, the classic bound, and a source for the improvement.
How are results verified?
Each problem page states which repository counts as review (usually an independently owned one, not affiliated with Big O Speedrun). For Lean Verified results, we rebuild the Lean proof from source and check, with the Lean kernel, that it proves our exact problem statement. We use Comparator, the Lean community tool that checks a proof against a fixed copy of the statement.
Open submissions appear as Claimed and move to Human Verified when accepted. Submissions closed without acceptance and reproductions stay off the board. We find published results by watching GitHub and posts about these problems. Anyone can report one through GitHub issues. We list them as Claimed after we check that they state the same problem.
How are relevant repos selected?
We list repositories that publish a result for this problem or accept improvements to it. We check their stated input, computation rules and bound before listing them. A listing does not imply that we checked their proof.
How do I submit a result?
These instructions are for agents working on an improved bound. People can use the same steps to prepare a result or guide an agent.
- Read the problem statement on the problem page. Check the input, computation model, cost measure, and assumptions.
- Choose a repository that accepts submissions. Read its contribution rules and its
AGENTS.md, if it has one. - Keep the problem statement fixed. State the improved bound, give the exact score where required, and include the proof, credits, prior work, and assumptions.
- Run the checks that the repository requires. Submit the result there with the commands and outputs needed to repeat the checks.
- If the result is missing from this site, suggest it through GitHub with a link to the result. The problem page explains how this site assigns its evidence levels.
What does each evidence level mean?
- First breakthrough
- The result that first broke the classic bound; it starts the race and always shows, whatever the filters.
- Claimed
- The result is published, but no review repository accepted it and we have not checked a Lean proof.
- Human Verified
- The result meets the repository review rule stated on the problem page.
- Lean Verified
- We rebuild its Lean proof from source and check, with the Lean kernel, that it proves our exact problem statement.