I spent a fair amount of my spare time this week diving into some ancient computer science from the 1970s, 1980s and 1990s (!!!), specifically Dana Angluin’s L* algorithm for learning a finite state machine from an oracle and Rivest & Shapire’s followups and extensions. Quite beautiful work in my opinion.

L* is especially simple and elegant imo. Shapire’s valiant is more computationally efficient and I think grounded a bit better, but a little harder to understand.

⤋ Read More