Post

@henryyuen.bsky.social I have heard you commented on the recent announcement by OpenAI on X, about one of the 10 problems very, very close to your own research. Would you be OK discussing it here as well?

Clément Canonne

@ccanonne.github.io

(same thing for @huckbennett.bsky.social and @noahsd.bsky.social , regarding the CVP one... If you have the time and energy of course!)

1/8/26, 8:44 pm0 reposts7 likes

Noah Stephens-Davidowitz

@noahsd.bsky.social

1 Aug

It's crazy. They didn't "only" prove hardness of CVP with a polynomial approximation factor. They also made the first improvement in decades on sphere packing AND on the optimal minimum distance of codes. (And they solved open problems in a bunch of other fields that I know less about.)

Noah Stephens-Davidowitz

@noahsd.bsky.social

1 Aug

It's difficult for me to separate the message from the messenger here. There's the fact that it was produced by AI. And, there's the fact (that @henryyuen.bsky.social also mentioned) that it's written pretty poorly. I think it will take some time to figure out what actually happened here :-/.

Clément Canonne

@ccanonne.github.io

1 Aug

That's fair. I think understanding what the "magic ingredients" are (deciphering the paper) is going to take a little time. (The fact that both of you mention the poor writing and exposition is quite interesting and sad (and upsetting), tbh.)

Chris Peikert

@chrispeikert.bsky.social

2 Aug

bsky.app/profile/chri...

Chris Peikert@chrispeikert.bsky.social

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!

Chris Peikert

@chrispeikert.bsky.social

2 Aug

Wrote some initial thoughts here: bsky.app/profile/chri...

Chris Peikert@chrispeikert.bsky.social

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/index/ten-ad...

openai.comTen advances in mathematics and theoretical computer scienceOpenAI shares new results on long-standing open problems in mathematics and theoretical computer science, including advances in geometry, cryptography, and complexity.