Lower Bounds via Gemini

I want to share a very interesting (and slightly surreal) update from last week on arXiv. Pratik, a PhD student at IMSC Chennai, just uploaded a new paper proving impressive new lower bounds in algebraic complexity. He gave significant credit to Gemini for helping him prove key lemmas needed for the result.

Generative AI has been helping solve Erdős open problems lately, but seeing that trend land “at home” in our niche of algebraic complexity feels like a milestone. It reminded me of a famous quote by Ran Raz that I read in Ramprasad Saptarishi’s lower-bound survey:

“So why are super-polynomial lower bounds (in algebraic complexity) still not proved? Maybe it’s because not enough people are working on it.” - Ran Raz

Looking at Pratik’s paper, I can’t help wondering whether we should update that sentiment:

“Maybe it’s because we haven’t spent enough tokens on it.”

I say that jokingly, of course.