1/ Initial reactions after some hours with this groundbreaking result proving the NP-hardness of poly-approx CVP/NCP: It is most likely correct, but more importantly, it is original, elegant, and beautiful! (Also: it is easy to improve, quantitatively.) openai.com
openai.com
2/ Strangely, Astra didn't optimize the polynomial approx factor! 1min with GPT-5.6 suggests that n^c -CVP is hard for **any c < 1/14** (not just c=1/400), simply by tightening up the bookkeeping. (Recall that c=1/2 is a fundamental barrier, where n^c-CVP is in NP \cap coNP.) 3/ Unsurprisingly, there are echos of prior hardness-of-approximation results: robust encodings via polynomials and "error correction" techniques (cf. PCP literature), power sums/moments (cf. Bennett-Peikert's simple NP-hardness of SVP), etc. 4/ But this result fires straight at the target via genuinely new ideas: no "gadgets," no PCPs, no gap amplification just 3SAT to NCP/CVP, via an elegant, highly novel encoding of the input formula as a collection of Reed-Solomon constraints. 🤩 5/ My and others' first reaction was that the paper is not well written. I've changed my mind on that. I spent >1hr on just the ~1-page proof overview. It is 𝐝𝐞𝐧𝐬𝐞 and 𝐭𝐞𝐫𝐬𝐞. It lacks helpful framing, but all key ideas are there. The paper's body is quite accessible! 6/ Sections 4 and 5 are where the magic happens and the new techniques flex their muscles. I am still working through them, and it will take some time to understand—especially how they yield polynomial gap factors. Exciting! 7/ Bottom line: If I were reviewing this for a top theory-of-CS conference, and the results bear out (as I expect them to), I would champion this for a Best Paper Award. (But I would also request a much more explanatory overview of the novel techniques in the intro...)