Researcher claims a simplified proof that ETH is false
A simplified proof of ETH is False [pdf]
Shiva Kintali presents a streamlined exposition of OpenAI's argument that the Exponential Time Hypothesis fails. For every fixed ε > 0, he gives a deterministic 3-SAT algorithm running in Cε(n + m + 1)^cε · 2^(εn) bit operations, combining sparsification, bounded occurrences, spectral replacement, and rational interpolation. The proof uses only elementary linear algebra, polynomial interpolation, and basic probability, and avoids assuming any of the new lemmas from the original paper.
The difficulty is that clauses link different groups. We remove these links algebraically.