Reposted by Lance FortnowFOCS 2026 @focs2026.bsky.social · 1hRegistration for #FOCS2026 is now open: focs.computer.org/2026/registr... Early bird deadline: ⏰ October 26, AoEfocs.computer.orgRegistration – FOCS 2026 013
Lance Fortnow @lance.fortnow.com · 1hA reader asks whether programming will help understand why there are still some problems that even the most powerful computers struggle to handle efficiently.blog.computationalcomplexity.orgDoes Programming Help You Understand Complexity?I got the following question in an email. My nephew is currently in high school in China and has developed a strong interest in computer ... 000
Lance Fortnow @lance.fortnow.com · 29/09/2026If I have seen farther, it is by standing on the shoulders of giant large-language models. 050
Lance Fortnow @lance.fortnow.com · 29/09/2026The correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola yield a proof that Almost-ParityP = BP.ParityP, from which you can get a simpler proof of Toda's theorem. Details:arxiv.org$\mathrm{Almost}\text{-}\oplus\mathrm{P} =...Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that... 030
Lance Fortnow @lance.fortnow.com · 28/09/2026The STOC CFP says "The use of AI tools will not be weighed in the evaluation of the paper by the PC." Bill wonders why then do they ask for AI disclosure at all.blog.computationalcomplexity.orgWhat is the points of AI-disclosure?The STOC conference (and likely others) are requiring that a submission says how much AI was used. I can imagine the following options: 1) A... 120
Lance Fortnow @lance.fortnow.com · 26/09/2026In my 1989 thesis I asked if there was an oracle separating IP from MIP. That was before we knew that MIP=NEXP, though that result doesn't relativize. Bouland, Huang, Natarajan, Shalit, Tal and Astra now answer the original question.arxiv.org$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not RelativizeWe construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson... 0111
Lance Fortnow @lance.fortnow.com · 24/09/2026Because PSPACE-Completeness still matters www.wsj.com/tech/ai/... 0102
Lance Fortnow @lance.fortnow.com · 23/09/2026This fall I'm joining the Leadership and Society Initiative at the University of Chicago, becoming a student where I started my academic career thirty-seven years ago. I hope to learn where I can best play a role to manage the weird times we are in. leadforsociety.uchic... 090
Lance Fortnow @lance.fortnow.com · 23/09/2026Breaking down the new STOC submission rules.blog.computationalcomplexity.orgThe New STOC Rules for the AI EraThe 59th ACM Symposium on the Theory of Computing takes place in Atlanta next June, part of the Federated Computing Research Conference . I... 051
Lance Fortnow @lance.fortnow.com · 21/09/2026Want to be Bill's student? He doesn't care about your major, your minors, your honors or your grades.blog.computationalcomplexity.orgI don't care about majors, minors, or honors programs. Do you? The following conversation is fictional. --------------------------- ALICE: (Looking over a student's record.) Hmm, let's see. She wants to ... 030
Reposted by Lance FortnowJeffrey Shallit 🇺🇦 @shallit.bsky.social · 18/09/2026A new risk for mathematicians: a colleague reports that immediately after they posted an abstract of their upcoming talk online, a student elsewhere used AI to derive proofs of the stated results and then posted it on the arxiv. My colleague hadn't posted to arxiv yet. Scummy. Watch out. 16219
Lance Fortnow @lance.fortnow.com · 17/09/2026The Manufacturing Tech show is back in Chicago and AI takes center stage, or does it?blog.computationalcomplexity.orgAI and Manufacturing ReduxITMS 2026 Two years ago I attended the International Manufacturing Technology Show in Chicago's McCormick Place and found a rather limited ... 000
Lance Fortnow @lance.fortnow.com · 17/09/2026STOC call for papers is out. Deadline is November 2. acm-stoc.org/stoc202... New rules for the AI era: limited submissions, public posting and a required video. Is it a coincidence that the camera-ready deadline is April Fools Day? 0125
Lance Fortnow @lance.fortnow.com · 17/09/2026Looks like every paper moving forward will have an AI declaration, even if it just says "We didn't use AI". 040
Lance Fortnow @lance.fortnow.com · 17/09/2026LAX is launching today, a way to connect natural mathematical language with Lean. They have a nice way to define complexity classes and can formalize some complexity results, for example nondeterministic space closed under complementlaxarchive.orgThe Immerman–Szelepcsényi Theorem — lax-733996Lax — an archive of formalized mathematical concepts and their proofs 082
Lance Fortnow @lance.fortnow.com · 16/09/2026I'm a fan of publishing everything. It's not like we'll run out of space on the Internet. The good stuff will bubble up through social media and AI-powered searching. 051
Lance Fortnow @lance.fortnow.com · 15/09/2026I thought about k-server with Howard Karloff when we were both young U Chicago professors in the 90s. We even came up independently (as did many others) with the work algorithm, and now we know it actually works. 040
Lance Fortnow @lance.fortnow.com · 14/09/2026Bill's take on all things AI and Mathblog.computationalcomplexity.orgMath, AI, and the Navier-Stokes EquationsOn September 1, 2026: LANCE: I'm surprised you haven't blogged about OpenAI solving 10 open math problems. BILL: If I post every time an op... 010
Lance Fortnow @lance.fortnow.com · 11/09/2026A tenet of the theory of computing is the interchangeability between program and data. So if an ML system uses a persistent writable memory, it could reprogram itself, potentially enabling recursive self-improvement, especially if many agents share the same storage space. 120
Lance Fortnow @lance.fortnow.com · 11/09/2026Given the rate of progress, pretty quickly if it happens at all. 010
Reposted by Lance FortnowRyan O'Donnell @booleananalysis.bsky.social · 10/09/2026Am 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.youtube.comComplexity Theory At Carnegie Mellon 05717
Reposted by Lance FortnowTerence Tao @teorth.bsky.social · 11/09/2026A group of 25 Fields Medalists, including myself, have made a joint declaration on Math and AI: mathandai.org . We welcome additional signatories. See also this article in the Economist announcing the declaration: www.economist.com/science-and-...mathandai.orgDeclaration — Math and AIRead the declaration and add your name. 422052926
Reposted by Lance FortnowOxford Mathematics @oxfordmathematics.bsky.social · 11/09/2026AI is ravenous and is eating mathematicians' lunch. A long-standing problem is solved, others are in its sights. But is this more than just a problem about problems? Here's Fields Medallist James Maynard. Read the Math and AI Declaration by 25 Fields Medallists: mathandai.org 11211
Lance Fortnow @lance.fortnow.com · 11/09/2026I suspect that would be a tougher cookie. It has many of the same barriers as P v NP. Ryan Williams' recent result gives a path to P <> PSPACE by TIME(t) in SPACE(t^epsilon) but I don't think it will go that way. 011
Lance Fortnow @lance.fortnow.com · 11/09/2026Technical when it needs to but mostly the story of the people behind it. It mentions other systems like Coq but the main focus is on Lean. 010
Lance Fortnow @lance.fortnow.com · 11/09/2026While P vs NP will remain out of the reach of AI, there are other complexity problems, like separating NP from L (log space) or BPP from NEXP, that might be more tractable and would still make an incredible splash. 251
Lance Fortnow @lance.fortnow.com · 09/09/2026Both OpenAI and Alpöge-Buckmaster heavily leaned on Lean in their Navier-Stokes announcements. Is this a new requirement for publishing?blog.computationalcomplexity.orgNavier-Stokes and LeanI was working on this week's post on Lean after reading Kevin Hartnett's book The Proof in the Code: How a Truth Machine Is Transforming Ma... 161
Lance Fortnow @lance.fortnow.com · 09/09/2026Another reminder that a solution to P v NP is not around the corner. Neither man or machine has even a viable approach. 3202
Lance Fortnow @lance.fortnow.com · 08/09/2026The post I wrote in January 2025, "Our Days are Numbered", is coming true much faster than I expected.blog.computationalcomplexity.org"Our Days Are Numbered"Slide in Lev Reyzin 's JMM talk "Problems in AI and ML for Mathematicians" Reyzin is paraphrasing Telgarsky. Posted with permission. Last we... 061
Lance Fortnow @lance.fortnow.com · 08/09/2026I used Claude to help me understand it all claude.ai/share/b4f1... I like how Claude discloses its conflict of interest since it was made by Anthropicclaude.aiClaudeShared via Claude, an AI assistant from Anthropic 011
Lance Fortnow @lance.fortnow.com · 08/09/2026OpenAI announces Navier-Stokes solution, but not without controversy openai.com/index/nav... And from earlier today: Tristan Buckmaster: cims.nyu.edu/~trista... Terry Tao (before the Open-AI announcement): terrytao.wordpress.c... I'm sure there will be more to comeopenai.comOn the Navier–Stokes Millennium Prize ProblemWe’re sharing an AI-generated solution to the Navier–Stokes Millennium Prize Problem, including a writeup and a formal proof in Lean. 182
Lance Fortnow @lance.fortnow.com · 04/09/2026Bill posts on the passing of Richard Stearns and his lesser known work on automata. blog.computationalco... 110
Lance Fortnow @lance.fortnow.com · 03/09/2026Richard Stearns died on August 29th at the age of 90. Stearns and Juris Hartmanis founded my field in their seminal paper "On the Computational Complexity of Algorithms" which earned them the 1993 Turing Award. Paper: www.jstor.org/stable... CACM Obit: cacm.acm.org/news/in... 0133
Lance Fortnow @lance.fortnow.com · 02/09/2026Computer science is as much about computers as astronomy is about the stars.blog.computationalcomplexity.orgWhat is a Computer?Ben Brubaker has a new Quanta essay Does Computer Science Need Computers ? Despite the title (and authors generally don't choose their titl... 000
Lance Fortnow @lance.fortnow.com · 31/08/2026Bill thinks I should care about colorblind presidents and vice-presidents because I myself am red-green colorblind. Well I didn't keep track. Turns out AI doesn't either. blog.computationalco... By the way I do use AI to distinguish colors for me so I don't always have to ask the wife.blog.computationalcomplexity.orgClaude and Colorblind QuestionsBILL: Lance, I have a question and a meta question: a) List all the presidents and vice presidents who were colorblind. b) Do you know this ... 000
Reposted by Lance FortnowBen Brubaker @benbenbrubaker.bsky.social · 28/08/2026My latest for @quantamagazine.org is something a bit different from my usual fare: a first-person essay exploring what theoretical computer science has to do with computers.quantamagazine.orgDoes Computer Science Need Computers? | Quanta MagazineThe theoretical side of the field doesn’t require computing machines. But many questions would never have been posed without them. 0326
Lance Fortnow @lance.fortnow.com · 26/08/2026Living through the calculator transition.blog.computationalcomplexity.orgThe Calculator TransitionThere's a scene in Apollo 13 where Jim Lovell, played by Tom Hanks, asks Houston control to check his calculations, which they do using a s... 020
Lance Fortnow @lance.fortnow.com · 25/08/2026Shafi Goldwasser, Adam Kalai, and Vinod Vaikuntanathan are creating a new non-profit Institute for Responsible Superintelligence for using theory to make AI safer. Read about the team at resi.org, sign up for their mailing list, donate, or reach out to hello@resi.org.resi.orgRESI OverviewRESI is a nonprofit research institute building the scientific foundations needed to make superintelligence safe by design. 140
Lance Fortnow @lance.fortnow.com · 23/08/2026Sad news from Hervé Moulin, the ousted editor of Games and Economic Behavior, a journal focused on game theory that had a long history of collaboration with the computing community. Elsevier "strategic priorities" guts yet another good journal. gametheorysociety.or... 271
Lance Fortnow @lance.fortnow.com · 19/08/2026Back to our regularly scheduled programming. Has any noticed that AI is getting much better at math?blog.computationalcomplexity.orgCentaur MathIn the past, new PhD students would ask how they could succeed when they had to compete with the likes of say, Richard Karp or Avi Wigderson... 0102
Lance Fortnow @lance.fortnow.com · 19/08/2026Computable90 conference at Bletchley Park Sept 16-18 celebrates the 90th anniversary of Turing's "Computable Numbers". Speakers include Avi Wigderson, Julia Knight and Rod Downey. www.tnmoc.org/comput... 071
Lance Fortnow @lance.fortnow.com · 17/08/2026Bill's thoughts on Illinois Techblog.computationalcomplexity.orgIIT is the canary in the coalmine (Do our younger readers know what that means? Do we have younger readers?)Lance has posted about his, and around 160 others, being laid off from IIT here .(IIT stands for Illinois Institute of Technology which is ... 041
Lance Fortnow @lance.fortnow.com · 14/08/2026From an old U Chicago newsletter, a picture of me using the new cutting edge technology, "Electronic Mail". 0401
Lance Fortnow @lance.fortnow.com · 12/08/2026This is how tenure ends.blog.computationalcomplexity.orgUnexpected UnemploymentEnjoying Idaho while ignoring Illinois Today is the first day of my life that I am unemployed. And not by choice. As I mentioned on LinkedIn... 3184
Lance Fortnow @lance.fortnow.com · 10/08/2026AI can prove theorems but only humans can give them funny names. Bill reports.blog.computationalcomplexity.orgMath Concepts With Funny Names(Some of this came from a Reddit post I read, and some of the comments on it.) Here are theorems with names that I think are funny or unu... 040
Lance Fortnow @lance.fortnow.com · 09/08/2026Isik 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... 1245
Lance Fortnow @lance.fortnow.com · 07/08/2026I'm back from vacation. Bill had two posts while I was gone on AI Erdős and Jeopardy. blog.computationalco... blog.computationalco... and in some personal news lnkd.in/p/gy_4aHrYblog.computationalcomplexity.orgWould Erdos have been happy with the resolution of the Erdos Unit Distance Problem? How to find out? Let's say there is a statement in math T that you wonder whether it's true or false. You may even make a conjecture of which way it goes. D... 181
Lance Fortnow @lance.fortnow.com · 07/08/2026Ming-Yang Kao, my former theory colleague at Northwestern, passed away last May.mccormick.northwestern.eduProfessor Emeritus Ming-Yang Kao Passes AwayKao, professor emeritus of computer science, passed away on May 11, 2026. He will be remembered for his contributions to the design, analysis, and implementation of algorithms and the development and broadening of computer science at Northwestern. 030
