“Efficient Lempel-Ziv Prediction with the Run-Length BWT” by OhadA

Audio note: this post contains a lot of mathematical notation. We narrate the simpler formulas and flag the complex ones, so you may want the original text to hand. 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: [...] --- Outline: (01:29) The prediction trinity (05:23) Matching the string's history (08:23) Going faster (12:37) Going even faster (15:39) Going fastest (20:58) Ending thoughts The original text contained 5 footnotes which were omitted from this narration. --- First published: November 5th, 2026 Source: https://www.lesswrong.com/posts/voe2dDnuopYn6DC3N/efficient-lempel-ziv-prediction-with-the-run-length-bwt --- Narrated by TYPE III AUDIO . --- Images from the article: Apple Podcasts and Spotify do not show images in the episode description. Try Pocket Casts , or another podcast app.