Helger Lipmaa

To my mind, this is OpenAI's most important TCS result yet (though I might be biased). And since it is posted by the venerable @rrwilliams.bsky.social , it must be true :o

From Pete Wayner.

youtube.com/shorts/wxMdr...

Our cryptography group grew again this semester. We're happy to welcome our new postdoc, Protik Paul (paul-protik.github.io), and new PhD students Rittwik, Arani, Kerim, and Calvin.

Over 400 academics in 30+ countries signed our open letter calling for immediate changes in AI development and deployment practices to ensure that cybersecurity incidents do not continue to occur, as future incidents will be far more damaging to our critical infrastructure.

A result of the recent OpenAI that should now be in every complexity theory course (as one lecture, if not more): there exist galactic algorithms. Of course this was known before, but it was not as obvious.

TCS part: page 12-16. UGC. Matrix multiplication. Integer multiplication (to name a few).

Goldreich’s short take on AI proofs is thought-provoking (and the Borges reference is quite on point). www.wisdom.weizmann.ac.il/~oded/on-pro...

TMLR has faced a deluge of submissions, necessitating stricter desk rejection policies due to limited reviewer capacity Co-EiC Nihar Shah reached out to authors of 10 papers slated for desk reject. Could they answer questions about their *own* submission? medium.com/@TmlrOrg/ask...

"This model has now resolved more than 100 long-standing open problems across most areas of mathematics." openai.com/index/adviso... terrytao.wordpress.com/2026/09/21/a... agmai.org

We finally finished the universal signature forgery for 1024-bit RSA! 2^32 oracle queries, 1200 core years precomputation, 180 core years for an individual forgery, and 3 years of human labor (no AI involved) by Laura, Adam, Nadia, Emmanuel and me to pull of this computation against real HSMs.

but who else should be using AI submission but people in the ML community who know AI inside out?

A different view. As a cryptographer (or maybe, as me - some cryptographers are in a different camp), I mostly agree with what @wtgowers.bsky.social is saying - my goal is to solve problems, and if AI does it better, then so be it. My problem is ethical. The way (say) OpenAI approaches it is wrong.

garymarcus.substack.com/p/two-dire-w...

Signed

“Now Lean, particularly in Navier-Stokes papers, is being used as a time-stamp, a way to claim your theorem before having to write it up properly in an explainable way.” A sentence that would’ve been seen as the ravings of a madman just ~1 year ago. blog.computationalcomplexity.org/2026/09/navi...

Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos. We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.

Millennium math problem solved by OpenAI may have "regurgitated" competitors unpublished work... also they spent more than $22 million in computing power in one week to scoop them. techcrunch.com/2026/09/08/o...

A blog post by the final boss

Dancing very very VERY close to saying “OpenAI stole our almost-complete proof of Navier-Stokes from internal access to our ChatGPT sessions because they were desperate to scoop Anthropic” which is absolutely 100% a believable thing OpenAI would do right now cims.nyu.edu/~tristanb/st...

Mathematicians and AI. Kraftwerk was so much ahead of its time. www.youtube.com/watch?v=6ozW...

I have complicated feelings about this

We quantified how much closer OpenAI's improvement over MRRW brings us to GV lower bound: at most 2%. Gain over MRRW: at most ~1%.

Like many others I was feeling the lack of a platform where the full spectrum of opinions (in particular also lesser heard voices) on "math and AI" may get an audience. Now here it is! Think about contributing and share it widely! proofsandprompts.com #math #mathsky #llm #AI #mathandai

We asked an unreleased research version of Claude to take a stab at the Riemann hypothesis. It didn’t solve it, but it did make strides on a related problem: it increased the lower bound for the fraction of zeros of the Riemann zeta function that satisfy the hypothesis from 41.6% to 67.2%.

who knew PIRs would be interesting :o

Markle tree - thee very British/snobbish Merkle tree

Isik Ulusan, a U Mass student, created Complexle, like Wordle but you guess complexity classes. For each guess you get hints (set-theoretic inclusion, the type of model it is defined on, uniformity, etc.) for a total of 6 guesses. Give it a try. iulusan.github.io/co...

This reminds me of the numerous stories about how wishes to genies backfire. AKA The Monkey's Paw (en.wikipedia.org/wiki/The_Mon...)

www.youtube.com/watch?v=7JwE...

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...

I wrote about OpenAI's Astra results, how AI will dissolve mathematics, and how people will cope about it: borretti.me/article/math...

OpenAI claim a proof that CPV is NP-hard for polynomial approximation factors. openai.com/index/ten-ad...

TCS+, the longest-running theoretical #computerscience seminar, will soon resume for the Fall. Let us know what you'd like to hear about (results, speakers, topics), and any suggestions you may have! sites.google.com/view/tcsplus... #TCSSky @tcsplus.bsky.social

next Greek epic for hollywood treatment needs to be Euclid's Elements. overdue

This is a very cool and exciting discovery by Claude Mythos! It found a serious 𝒎𝒂𝒕𝒉𝒆𝒎𝒂𝒕𝒊𝒄𝒂𝒍 attack on the post-quantum signature scheme HAWK, an "on-ramp" candidate for potential NIST standardization. www.anthropic.com/research/dis...

New York University professor Hong Wang has won the Fields Medal for her work three-dimensional Kakeya set conjecture, inspired by a simple question that has puzzled mathematicians for more than a century. But what is a “Kakeya-type” problem?

Domagoj Bradač gives a tight exponent for the smallest n, such that any graph on n vertices has either a clique of size s or an independent set of size k. For fixed s and large k, n is k^{s-1} up to polylog factors. A major result in Ramsey theory.

SNARGs for NP from Unprovability of Mathematical Theorems (Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, Surya Mathialagan) ia.cr/2026/1180

Correlation Intractability for all Batched Relations (Damiano Abram, Giulio Malavolta, Lawrence Roy) ia.cr/2026/1140

On the Impossibility of SNARGs with Short CRS (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting) (Liyan Chen, Zhengzhong Jin) ia.cr/2026/1144

AI in education = commercialisation of a collective responsibility outsourcing a social, civic, and democratic process of cultivating the coming generation to commercial and capitalist enterprise whose priority is profit

Huge congratulations to Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart on being awarded the Gödel prize for their breakthrough work on algorithmic robustness! www.sigact.org/prizes/g%C3%...

As US science funding becomes more limited, more bureaucratic, more political, we turn more to industry and foundations to help fund and set our research agenda. And now we have to deal with the consequences. My thoughts on yesterday's State of the Sciences Address:

youtu.be/5GUcvSAJcJw?...

Wow! Alfred Menezes just published this 182 page "A Gentle Introduction to Lattice-Based Cryptography" paper. I just skimmed through it, but it looks like an invaluable resource if you want to study lattices and how they're used in (PQ) Cryptography. eprint.iacr.org/2026/1098

📢 2026 ERC Advanced Grant call is open for applications! Are you an established, leading researcher who needs long-term funding to pursue a ground-breaking research project? The ERC Advanced Grant could be for you. Application portal 👉 link.europa.eu/QCDXct #ERCAdG #research #grant #funding

“The sum-product conjecture is false for real numbers” THOMAS F. BLOOM, WILL SAWIN, CARL SCHILDKRAUT, AND DMITRII ZHELEZOV A human proof that exploits the same kind of “tower of fields” that was used in the AI-generated counterexample to the unit-distance conjecture!

In the last 48h: - Jr researcher asked me wheter to use AI in making talks - Saw two talks, with AI {slop, enhanced} slides Collected my thoughts and wrote a post. Tl;dr: don't steal your own thinking, don't remove *you* from your talks. Also, give a &#@% about your talks.