Wednesday, October 28, 2026

AI Just Rewrote the Textbooks. Now What?

 

The foundations of computational complexity theory were just shaken.

Recent algorithmic breakthroughs generated by frontier AI models have shattered long-standing mathematical assumptions. Specifically, research models from Anthropic and OpenAI have concurrently refuted the Exponential Time Hypothesis (ETH), alongside the 3SUM and All-Pairs Shortest Paths (APSP) conjectures.

These are extraordinary, textbook-rewriting developments. However, concluding that decades of research built around these conjectures was pointless fundamentally misunderstands what that research actually proved -- and what makes theoretical inquiry valuable.

Many hardness results in computational complexity are framed as conditional implications:

“If problem A cannot be solved this quickly, then neither can problem B.”

The proof constructs a translation from A to B, carefully controlling how much the problem instance grows via this translation. We call this a reduction. A sufficiently fast algorithm for B would then give a sufficiently fast algorithm for A.

The hardness of A is a provisional assumption. The reduction itself is a proven, permanent mathematical fact.

Much of modern cryptography follows this exact same pattern. An efficient attack on a cryptographic scheme would yield an efficient algorithm for an underlying mathematical problem. The security conclusion depends on that problem being hard; the proof establishes the unbreakable connection between them.

When the assumption falls, something substantial is lost. We can no longer use it to justify a claimed computational barrier. But the reduction remains entirely correct. The relationship between the problems survives.

In fact, those very relationships are what allow an algorithmic breakthrough to spread from one problem to dozens of others. The new 3SUM and APSP work explicitly exploits previously known reductions to unlock further consequences. Mathematics developed to map hardness is the exact tool we need to exploit unexpected easiness.

There is a vital lesson here for how the scientific community communicates results.

Moving forward, we should explicitly state the exact mathematical relationship we actually prove, detailing its quantitative bounds. The conjecture-based hardness conclusion should follow strictly as a secondary corollary.

For a simple illustration, a sparse 3-SAT instance with n variables and a proportional number of constraints can be translated into a vertex-cover problem on a graph with a proportional number of vertices. That rigid control over size is what allows us to relate the running times. This translation remains deeply meaningful and potentially useful in a completely different context, regardless of whether ETH stands or falls.

Researchers often already state their results this way. We should give those relationships more importance, especially when explaining our work beyond our immediate community.

Fine-grained complexity gave researchers a reason to hunt for unusually economical (or fine-grained, as we like to call them) reductions. That exploration produced techniques and connections that might otherwise have remained undiscovered. A conjecture can be false and still have been a useful question to investigate. Its eventual refutation does not, by itself, make investigating it unreasonable.

This highlights a deeper concern regarding AI in pure research -- a vulnerability being highlighted by many mathematicians, but one that the broader community frequently misses.

If an AI system had simply supplied the final answer before this decades-long exploration began, which intermediate discoveries would we still have made? Which foundational questions would we have never thought to ask?

We cannot know. Earlier answers can open new directions, and AI can help explore them. But there is a distinct risk in treating a finished statement and proof as the absolute end of an inquiry. We may move on before discovering what else the question had to teach us. Even a correct proof can arrive far too early -- long before we have fully explored the surrounding landscape of ideas.

That possibility deserves serious attention as we decide how to integrate these systems into academic research. We must explicitly value the deep understanding developed through exploration alongside the raw answers obtained.

And we must remain curious, even when the answers surprise us.

Stay hungry. Stay foolish. Even if AI is smarter than you.

Beyond all this sometimes unwanted light, there will still be that familiar darkness: things we do not understand, questions we have not learned to ask, and room to find meaning for ourselves.

Theoretical Computer Science in an Era of Proof Abundance

 In my previous article, “How AI-Powered Research Might End an Era of Human Ego,” I wrote about the unease of watching artificial intelligence dismantle traditional benchmarks of human intellectual supremacy.

For decades, theoretical computer science operated under an implicit scarcity model. Important proofs were rare, difficult to produce, and usually represented years of sustained human effort. The difficulty of producing a paper acted as a natural filter on how many papers entered the scientific ecosystem.

As Terence Tao has recently put it, we are moving from an era of proof scarcity to one of proof abundance.

We are approaching a world in which AI systems can resolve difficult open problems and generate dense, valid mathematical arguments at a scale humans cannot match. The traditional bottleneck is therefore shifting. It may soon no longer be the generation of proofs, but their verification, digestion, and explanation.

If an algorithm produces ten thousand pages of correct proofs overnight, we have obtained ten thousand pages of mathematical truth. But we have not necessarily created ten thousand pages of shared scientific knowledge.

Science progresses only when a competent community can understand what has been established, determine that it is correct, recognize why it matters, and connect it to the rest of human knowledge. In an era of proof abundance, we can no longer measure progress merely by how many results have been written down. We must increasingly measure it by what the scientific community has meaningfully understood and accepted.

Our truly scarce resource will be human attention.

To prevent theoretical computer science from collapsing into a sea of technically correct but collectively undigested text, we need to move from a culture of maximum production to a culture of intellectual ownership and reciprocal responsibility.

I propose the following framework.


1. Strict Submission Caps

The policy: No researcher should be listed as an author on more than two submissions to any single edition of a designated flagship conference—for example, STOC, FOCS, SODA, CRYPTO, EUROCRYPT, ASIACRYPT.

The cap should count submissions, not acceptances.

The rationale: Every submission asks a scientific community to spend the only scarce resource -- expert attention evaluating it. The relevant resource is therefore consumed before the paper is accepted or rejected.

A per-venue cap protects precisely this resource. Someone may legitimately work in several different communities and submit one paper to each of them. What should no longer be possible is for one researcher to place six, eight, or ten papers before the same program committee at the same deadline.

The cap forces a real choice. Before seeing which papers will be accepted, researchers must decide which one or two results are important enough to ask that particular community to evaluate.

AI may soon allow an individual researcher to produce technical material at something approaching the rate of a present-day research group. Our submission rules cannot continue to assume that generating a polished manuscript is itself evidence of sustained human investment.

This is not a restriction on how much anyone may think, discover, or communicate. It is a restriction on how much of the community’s limited reviewing capacity any one individual may demand.


2. The Reciprocity of Scientific Attention

The policy: Researchers who regularly ask the community to evaluate their work must accept a comparable responsibility to digest, verify, review, and explain the work of others.

Conferences, universities, and funding bodies should recognize serious reviewing, verification, exposition, as central scientific contributions—not as invisible academic service. Maybe reviewers, who provide useful advice can be listed as co-authors (after all, here we have someone spending the most scarce resource -- human attention)

The rationale: In a healthy research culture, a competent researcher should spend at least as much serious intellectual time with the work of others as writing and promoting their own work.

Science cannot function if everyone wants to be an author and no one wants to be a reader.

Every paper creates work. Someone must check the proof, compare it with previous results, understand its limitations, extract its central ideas, and explain those ideas to others. As proof generation becomes easier, this work becomes more—not less—important.

In the era of proof abundance, identifying which results are correct, important, useful, or genuinely new may be as valuable as producing another proof.

Submission caps are not merely a mechanism for reducing volume. They create time and incentives for researchers to participate in the collective understanding of their discipline.


3. The Practical Dissolution of Courtesy Authorship

The policy: Senior researchers do not need to place their names on a student’s paper unless they made a substantial intellectual contribution to the result.

Advising, encouraging, providing funding, or offering general feedback does not automatically justify authorship. Professors can—and should—help students without necessarily becoming coauthors.

The rationale: Under a strict submission cap, courtesy authorship becomes costly and will therefore largely regulate itself. A senior researcher can no longer attach their name to many papers merely for prestige, institutional credit, or funding purposes without spending their own scarce submission opportunities.

This would help prevent established researchers from accumulating disproportionate ownership of work primarily done by students or junior collaborators.

It would also give emerging researchers a less obstructed opportunity to speak in their own names, stake their own claims, and be evaluated on the merits of their work.


4. The Proof-of-Understanding Lecture

The policy: At the time of submission, every paper must be accompanied by a public, long-form digital-whiteboard lecture, normally lasting one to two hours.

This should not be a polished slide presentation that can be AI-generated or a narration of prepared script. The presenter should begin with a blank whiteboard and develop the definitions, examples, diagrams, equations, and proof arguments by hand on a tablet or whiteboard while speaking.

If several authors made distinct technical contributions, they may divide the presentation appropriately. Each named author must be willing to answer questions about the contribution for which they claim credit, and at least one author must be able to explain the entire logical structure of the result.

Reviewers should also have the option of requesting a live online technical discussion with the authors. In such a Zoom call, reviewers could ask unannounced questions, request that a delicate step be reconstructed, ask why a particular assumption is necessary, or explore what happens when the argument is modified.

The rationale: A polished paper is no longer reliable evidence that its nominal authors understand what appears under their names. Nor is a polished slide presentation sufficient: AI can already generate slides, scripts, diagrams, and narration.

A handwritten lecture developed in real time creates a much stronger test. Writing mathematics while explaining it requires the presenter to handle the notation, reconstruct the logical dependencies, and communicate the intermediate reasoning that polished prose can hide.

The subsequent possibility of unscripted questioning makes it considerably harder to simulate understanding merely by memorizing or reading AI-generated material.

No method can prove that every idea originated entirely inside a human mind, and we don't need to try to do this. That is not the appropriate standard. AI assistance should be permitted and disclosed.

The relevant standard has to become human intellectual ownership: identifiable human authors must have absorbed the result sufficiently to reconstruct it, explain its central ideas, answer technical questions, and accept responsibility for its correctness.

Reasonable accommodations should, of course, be available. The requirement is command of the math, not theatrical performance, accent, or fluency under time pressure.


5. The Video—not the Paper—as the Scientific Timestamp

The policy: Posting a manuscript or preprint, including on arXiv, should not establish recognized scientific priority.

The public posting time of the qualifying handwritten lecture—released when the corresponding paper is formally submitted—should be the provisional scientific timestamp of the result.

The video (which is linked to the peer-reviewed submission), not the paper, is the timestamp.

That timestamp becomes certified when the result is validated through peer review and, when necessary, an oral discussion with the authors.

The rationale: If an ordinary arXiv upload continues to establish priority, submission caps will be easy to circumvent without technically being violated.

Researchers could generate and upload large inventories of AI-assisted papers, associate their names with dozens of results, and then submit those papers gradually over subsequent years. The reviewing pipeline would be limited, but the priority and prestige pipeline would remain unlimited.

An arXiv upload may still communicate an argument, invite criticism, and establish the historical fact that a document was publicly available on a certain date. But it should not indefinitely reserve scientific territory.

To claim recognized priority, researchers should have to do three things:

  1. Spend one of their scarce submission opportunities.
  2. Publicly explain the result through a handwritten technical lecture.
  3. Remain available to answer expert questions about it.

This forces researchers to decide which results they are genuinely prepared to understand, defend, and ask the scientific community to certify.

If two independent groups submit correct solutions to the same venue during the same submission cycle and both provide qualifying explanatory lectures, both papers should normally be accepted. One should not be rejected merely because the other group posted its video a few hours or days earlier.

In a world where AI performs much of the technical labor, associating one’s human name with a mathematical truth is already a significant privilege. We should not insist on monopolizing that truth merely because we reached the upload button marginally earlier.


Curation Over Production

This framework is deliberately restrictive. But the alternative may be the eventual collapse of human peer review and a rapid transition from AI for science to science by AI, reviewed by AI, and intelligible only to AI.

The purpose is not to preserve a fictional world of AI-free research. That world is disappearing.

The purpose is to preserve a human scientific community. The solution isn't perfect, but seems reasonable to me.

Researchers should not have an unlimited claim on the community’s scarce attention merely because AI has given them an effectively unlimited capacity to produce manuscripts. The right to ask others to understand our work must be accompanied by a willingness to understand theirs. The right to claim a discovery must be accompanied by a willingness to explain and defend it.

AI may give us answers. But it remains a human responsibility to decide which answers matter—and to ensure that they mean something to the rest of us.

Disclosure: The central arguments and policy proposals in this article are mine written over a few days, and collects my thoughts over the last few weeks. Gemini was used to help edit and reorganize the text.

How AI powered research might end an era of human ego

 Over the past few weeks, I have been extremely disturbed by the progress that AI has made, and how it is going to affect humanity, and whether there is anything positive that we can take away from it. I have a lot of unanswered questions, but in the following, I try to suggest the most optimistic thoughts.

I have had in the last few weeks regarding AI being better than humans at scientific discovery. How AI powered research will end an era of human ego. For the last 500 years, the definition of scientific progress has been very tightly connected to the human ego. We have associated every development with the developer. We built massive legal, academic, and economic structures, patents, publications, awards designed to answer a single question -- which individual gets credit for a certain discovery, who do we associate a discovery to. But as artificial intelligence starts to be better than all humans at solving research problems, humanity is facing an existential crisis. If a machine makes the breakthrough, who owns the truth?

The answer to this dilemma should force us to look backward, not forward. When viewed through the deep lens of history, our obsession with individual human attribution is not eternal -- it is only a 500 year old phenomenon. By removing the human name from the discovery, AI is perhaps not breaking science -- it is returning it to its ancient roots.

Before the Renaissance, the idea that a human "owned" an idea or a discovery was alien. The Archimedes Principle, the Kepler's laws, the Pythagorean theorem, all got their names hundreds of years after they were discovered, and some of these names were only chosen via anecdotal evidence which wasn't necessarily accurate. Since humans decided to attribute humans to discoveries, we forced these names to "correct history". Before that, for thousands of years, knowledge was perhaps viewed as a pre-existing fabric created by nature. Humans did not create ideas; they were merely granted the privilege of finding them.When a breakthrough occurred, gratitude was perhaps directed upward to God, or outward to the community, not inward to the self.

Knowledge belonged to the collective heritage of humanity. There were no patents, no copyrights, and no academic tenure tracks. The value of a discovery was measured solely by its utility: Did the new crop rotation system prevent famine? Did the herbal remedy cure the fever? The name of the peasant or monk who first noticed the pattern was irrelevant to history, lost to time because it simply didn’t matter.This collective, humble view of knowledge changed somewhere  between the 15th and 17th centuries.

The shift was driven by a storm of cultural, economic, and technological shifts. For 500 years, this system has worked spectacularly. The promise of wealth, fame, and historical legacy motivated generations of humans to push the boundaries of knowledge. But it also hardcoded a dangerous assumption into our culture: that science cannot happen without human ego. Arguably, perhaps science has progressed better than it would have if we hadn't associated human ego to it.

Today, artificial intelligence is shattering that assumption. AI is making scientific breakthroughs at a pace no human can match. The source of these discoveries is the human data we have created over centuries, but often it is impossible to trace, what led to a particular discovery. Just like a Ramanujan had some divine power whisper an answer in his sleep, modern mathematicians often cannot explain how the AI arrived at its conclusion. In future, it will be even more so. The AI simply presents the truth. Once again, humans find themselves acting not as the grand creators of knowledge, but as the humble communicators of knowledge they did not create themselves.

AI has no ego. It provides us breakthrough results on a platter. It will never demand a higher salary, sue for patent infringement, or step onto a stage to accept a Nobel Prize. It processes the sum total of human data, spots the hidden patterns, and hands the answers back to the collective.

The world has come a full circle, perhaps. Our current anxiety surrounding AI discovery is not a technological problem; it is a cultural friction. We are trying to force a non-human, collective intelligence into a human-centric reward system built in the 1500s and that we have cherished for 500 years. Patent courts around the world are currently struggling with debates over whether an AI can be listed as an "inventor." Journals are asking whether AI can be listed as a co-author. We are panicking because our modern systems require a human name to function. So, we are trying to adapt to a system where a human communicating an AI generated solution is an "author".

But perhaps, we are missing a divine signal. The machine is offering us a liberation from this 500 year old practice. By removing the human ego from the center of discovery, AI allows us to end this 500-year-old detour. It invites us to return to an era where the validity of a truth is not dependent on the identity of its discoverer. We can stop asking who gets the credit, and start focusing entirely on how the discovery can serve the common good.

The difficulty, and this is a massive difficulty, is that we haven't gotten enough time to adapt to this change. We will have to learn and adapt to live in this new world very very quickly -- maybe within months. Perhaps, we should quickly revisit ancient texts and learn from our ancestors from the pre-1500 era.