Doug Colkitt: OpenAI problem #109 tightened further to κ = 2^-78
Doug Colkitt @0xdougX
Why it matters
Highest-reach post of the series (~135k views): second conditional tightening, to κ = 2^-78, via nonadjacent axis swaps.
Summary
Posted 13:56 UTC. Claims κ = 2^-78 (a 2^104-fold improvement over OpenAI’s 2^-182) by using nonadjacent axis swaps, which the original manuscript already supported, to cut layout routing from O(d²) to O(d) swaps; the earlier ceiling no longer applies to the new witness. Quotes the 02:24 UTC post.
Archived text
We are publishing an update to OpenAI Problem #109 (integer multiplication) with a substantial further tightening:
T(n) = O(n (log n)^(1 − κ)),
With κ = 2⁻⁷⁸ (tightened from κ = 2⁻¹⁸²)
Approximately 570 million fold improvement over our previous result and a 2¹⁰⁴ fold improvement over original OAI result.
Our earlier ceiling applied to a cubic bottleneck in the network. The new witness scales quadratically; we haven’t established a new ceiling.
The key was using nonadjacent axis swaps to route around the cubic bottleneck. The original manuscript already supported nonadjacent axis swaps. Using them directly reduces layout routing from O(d²) to O(d) swaps.
Quoting @0xdoug: We’re publishing a result demonstrating a substantial tightening to the results from OpenAI Problem #109 (integer multiplication).