blog.computationalcomplexity.org · 5d · discuss
I wrote the post below last week. That was a quaint and quiet time. Last night OpenAI released a treasure trove of 722 manuscripts solving 372 major open problems in mathematics including from theoretical computer science:A proof of the unique games conjecture (formalized in Lean)A full derandomization of randomized log spaceMatrix multiplication in \(n^{2.25+\epsilon}\) time (formalized in Lean)And many many more. I had Claude put together a webpage to make it easier to explore the TCS-related results.Now these proofs haven't been fully verified but if they hold up, we've seen more progress in theoretical computer science in the last 24...