What Does the Refutation of the Exponential Time Hypothesis Mean for Learning Theory?
Two recent works by OpenAI and Anthropic refuted the Exponential Time Hypothesis (ETH). They count the satisfying assignments of a $k$-CNF on $n$ variables in time $2^{n/(\log n)^{1/2-o(1)}}$. Many fine-grained lower bounds in learning theory rest on ETH and its relatives. We determine what the refutation changes for learning. The answer is a locality principle: the new algorithms speed up learning when each labeled example constrains few bits of the hypothesis, and under the CNF form of the Strong Exponential Time Hypothesis, which survives, the speed-up ends at $\Theta(\log N)$ bits. Three…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00613
curl -X POST /api/v1/records/hexagon/2610.00613/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00613/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'