Description du poste
The Lempel-Ziv parse of Chad Gadya (חד גדיא), right-to-left, drawn as an arc diagram. Generated by Claude Opus 5.5
I have published a new paper on efficient string prediction. It was written during the PIBBSS 2026 summer fellowship, under the mentorship of Vanessa Kosoy.
This research builds on Kosoy's previous work in stringology. Kosoy built a polynomial-time algorithm for predicting repetitive sequences and I have used other algorithmic techniques to further decrease the runtime.
The goal of this post is to explain some of the ideas from Kosoy's paper and how my work builds on them. My writing will be mostly informal; the field of string algorithms has a lot of technical jargon which I will not try to fully explain. I hope to mostly communicate interesting ideas and topics I've bumped into during the research, while linking to external resources for anyone who wishes to learn more.
The prediction trinity
There are three things we want every good predictor to have:
• Power: can predict general, real-world patterns.
• Efficiency: can run in practice.
• Formal guarantees: we can prove what it can or can't do.
Unfortunately, no framework today satisfies all three properties at once.
Deep learning is powerful and efficient, but lacks a strong framework of formal guarantees. (This might be a problem!)
Solomonoff induction / AIXI are extremely powerful, and have formal guarantees, but can't actually run in practice.
My research is on the third edge: efficient algorithms with formal guarantees, though ones that are still not powerful enough for "actual" intelligence.
Of course, classical learning theory already has plenty of efficient algorithms with provable guarantees (e.g. linear regression). However, these algorithms assume the shape of the hypothesis is fixed in advance and learn its numerical parameters; our algorithms learn compositional structure, as described in Kosoy's compositional learning theory. (Deep learning also learns numerical parameters, but