{"id":"arxiv/2611.00517","url":"https://arxiv.org/abs/2611.00517","tags":["cs.CC","cs.DS","math.CO"],"score":0,"title":"Limits and Constants of OpenAI's Claimed ETH Refutation","domain":"cs.CC","source":"arxiv","authors":["Fabio Dias","Yvens Lima"],"reviews":0,"subject":"cs.CC","summary":"A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a $k$-CNF formula in time $2^{O_k(n\\log\\log n/\\sqrt{\\log n})}$, and $2^{O(n/\\sqrt{\\log n})}$ at bounded clause density, which would refute the Exponential Time Hypothesis. The headline bound is proved by tensor contraction; the body develops an interpolation algorithm with the weaker exponent $n(\\log\\log n)^2/\\sqrt{\\log n}$. This note does four things. First, it explains the interpolation algorithm in plain terms. Second, it asks how large $n$ must be for the bounds to bite. The preprint…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}