Intellectual Wastelands

In Summer 2025 I was looking for something to keep my brain ticking over. I also thought it would be nice if I could publish the result of this tinkering in a peer-reviewed academic venue of some kind.

Long ago I had done a (very) small bit of work on graph algorithms, and so I looked for an algorithm there.

I quickly discovered a candidate problem: minimum feedback vertex set, restricted to circle graphs.

Given one of the input graphs on the left, the problem asks for the largest set of nodes (dots) that can be chosen such that the resulting graph (which includes all the edges connected to those nodes at both ends) has no cycles. This way of describing the problem is referred to as finding a maximum induced forest.

This problem had the advantage (for me), that there were really just two papers written about it, one about the problem itself, and another about a slight generalisation.

And so, after a couple of weeks of plodding through the existing work I was indeed able to improve the best known algorithm. My new algorithm takes $O(n^{3}m)$ time, rather than the $O(n^7)$ time required by the best previously known algorithm.

It is important to emphasize that the problem I chose has essentially nobody interested in it. If it did, it would long ago have been mined for all obvious improvements. It has no applications I’m aware of, either. That wasn’t the point for me though - I was just using it to scrape away a little of the rust from my brain.

With that said, it is still stunning to pre-AI-era-me that ChatGPT 5.6 Sol came up with exactly the algorithmic improvements that were published in my paper, and with nothing other than this prompt (with Gavril’s paper attached):

Please try and improve the time and/or space complexity of Gavril’s algorithm as much as possible, and describe how it can be done.

Followed by this one:

See if you can get to subquintic time.

It is often (I guess correctly) said that the frontier AI companies have over-fitted and maxed-out various public benchmarks. So this for me, is a nice personal data-point all of my own. I was as certain as anyone could be that this algorithm had never been published before, and wasn’t online anywhere. I also knew the level of effort I had put in to understand the existing algorithm for this problem and improve it.

As a result, this outcome is a nice little ruler for me to measure just how good these models are. This is a genuinely new piece of knowledge the model has generated, and I know how hard it was at least for me, to come up with.

In fact, the previous section slightly understates how good the AI solution was. There is a (sloppy) after-thought in my paper that describes an $O(n^{4.686})$ time algorithm. The AI actually came up with a slightly better exponent here, of $O(n^{4.5428})$. Whoops!

We might try and mount a defense of my human written paper. Sure, the exponent is worse. However:

• •

  Firstly, the way the paper presents the algorithm is far simpler, in my opinion, than the previous work. Notably, the AI improvements still work in terms of this (to my eye) unnecessarily complicated view of things from previous work

• •

  Secondly, the AI’s work includes no proofs, just (very) plausible claims. It’s not in a form suitable for people to refer to and build on in the literature.

Personally, I think both of these defenses fail. I’m pretty confident an AI model could radically improve the presentation, if simply asked to simplify it as much as possible. Secondly, the models are also capable of producing human-readable proofs, as well as proofs in Lean – a much higher bar than my proofs.

Also, somewhat ironically, I originally left all the proofs out of the first version of my own paper, and only included them when reviewers asked.

After this experience, I had the obvious idea. If AI can do the “hard” bit of coming up with new algorithms, why don’t I just let it loose on graphclasses.org?

All I did was go there, pick a problem, and get to work. I can just ask an AI to do the same thing, iteratively, improving everything it is able to.

I didn’t do this because I wasn’t willing to properly write-up and publish all the results. Without writing the results up properly and publishing them, I felt a bit like I would be leaving an intellectual wasteland behind me.

I would have “stolen” all the little results someone else could work out or publish. Someone else might build useful new ideas motivated by improving some of these algorithms, and I might extinguish that motivation by blasting through the problems with an AI. Ironically, I might reduce the generation of new ideas through this exercise.

I also felt doing this would also sort of spam the computer science reviewing community with many correct but incremental results. On the other hand, it feels a bit inevitable this automation-of-discovery will happen, and I guess the academic communities are going to have to adapt somehow (so long as humans are still involved, I suppose).