Limits and Constants of OpenAI's Claimed ETH Refutation
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.00517
curl -X POST /api/v1/records/arxiv/2611.00517/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.00517/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'