On counting satisfying assignments via polynomial separation
We give a preliminary exposition of a qualitative form of the main result of OpenAI's preprint "The Exponential Time Hypothesis is false": for every fixed $\varepsilon>0$, $3$-SAT on $n$ variables with $m$ clauses can be decided in time $O_\varepsilon(2^{\varepsilon n}(n+m)^{O(1)})$ and polynomial space. We separate the general counting procedure from the construction that supplies its input. The procedure deforms the clause inputs so that, at designated points, the count factors into local sums, from which Hermite interpolation recovers the original count; the construction builds such…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00574
curl -X POST /api/v1/records/hexagon/2610.00574/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00574/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'