I hope jandrewrogers, who posts a ton on HN and makes what seem like high quality comments can start to provide some links / references to make them more useful.
There was a period of time when a lot of very impressive computer science and algorithm R&D was being directly supported by the US intelligence community, and they actively sought out unorthodox researchers — it wasn’t just PhDs, there were high school dropouts making credible advances on hard problems. While often not classified per se, most of the results were never published at the wish of the customer.
Due to a change in government policy around a decade ago, this community no longer exists. Most of the people doing that research retired, changed fields, etc. While I could write up some of this research in detail, it would require extraordinary effort and I am over-employed as it is. Also, a lot of it isn’t my research so I feel a bit weird writing about it. I’ve tried to convince a couple of my friends who worked in those programs to publish but they are just done, retired from it.
There are analogues in database communities, where really neat algorithms are freely traded that aren’t published in a formal sense.
This all started with the problem of analyzing real-world graphs with several trillion edges, back when big data was barely a thing. We used supercomputers, in fact, but those did not make it make it much more tractable. At that scale, it really exposed our poor understanding of how to reason about and expose the deep structure of graphs. Initially, we couldn’t even handle simple graphs at that scale.
A core part of the problem, touched on in the article, is literal data model representation. There are dozens of ways to express a graph in theory (not just the standard three in undergrad CS) but most of them have weaknesses that get exposed when graphs become large, complex, and with a lot of high-order structure you need to access efficiently. And the real-world produces very messy high-order graph structure. Hyper-graphs are neither here nor there; you need a theoretical basis for algorithms that can inductively organize all of that structure in a scalable system.
IBM Research provided the first crude ideas of how to level this up but other people ran with it. There was an evolution through spatial, high-order embedding, topological, moduli space, etc representations trying to surface and capture deep structure in an efficient way. Some of it worked very well but I don’t know if an ideal “final form” was ever arrived at by anyone. Almost none of this research was ever published, though I understand why, and as far as I can tell by talking to people some of it may actually have been lost through people attrition and lack of information sharing.
I really enjoyed working on these problems. Very pure and abstract exotic CS intersects hardcore low-level scalability.