NP-Incompleteness
LZ77
05 Sep 2026
Jacob Ziv and Abraham Lempel were both faculty at the Technion in Haifa, Israel, when in 1977 they published a paper called A Universal Algorithm for Sequential Data Compression in which they described a compression algorithm which, unlike Huffman coding, doesn’t rely on knowing the frequency of symbols upfront.
Ziv was an information theorist from the Electrical Engineering department while Lempel was part of the Computer Science department. They met due to their interest in lossless compression and Ziv said [1] that their skills complemented each other well:
I knew all about information theory and statistics, and Abraham was well-equipped in Boolean algebra and computer science.
This algorithm is now known as LZ77 (their last name initials + the year the paper was published). A popular algorithm called DEFLATE combines LZ77 with Huffman and is used by tons of software including gzip, git, png, etc.
In this post we’ll cover the LZ77 algorithm.
CacheLib
28 Aug 2026
CacheLib is an open-source C++ library from Meta for constructing in-process caches. At a high level, we can think of it as a hash table in memory with the option to spill to flash storage.
In this post we’ll study this library, mainly the in-memory portion based on the paper The CacheLib Caching Engine: Design and Experiences at Scale [1] and the code.
Asymmetric Numeral Systems
20 Aug 2026
Jarosław Duda is a Polish professor at the Jagiellonian University in Kraków. He developed a family of entropy coding methods called asymmetric numeral systems (ANS), mainly used in data compression. He wanted these to remain patent-free but has had mixed success.
Google worked with Duda around 2014 in a paper Mixed boolean-token ANS coefficient coding and tried to patent a coder for video, but Duda pushed back and Google abandoned the attempt. In 2019 Microsoft was able to patent a variant and since then other patents have been granted internationally.
A variant of ANS, known as FSE, is used by Meta’s compression library called zstd. I wanted to learn more about it and decided to study this algorithm first.
Euclidean Minimum Spanning Tree
17 Aug 2026
Otakar Borůvka was a Czech mathematician who is best known for his work in graph theory. Once, his friend Jindřich Saxel, an employee of the West Moravian Power Company, asked him for help optimizing electric distribution networks.
Borůvka modeled the problem as the minimum spanning tree problem and then came up with the first known algorithm to solve it, now known as the Borůvka algorithm.
In this post we’ll explore the Borůvka algorithm combined with KD-trees to solve the Euclidean Minimum Spanning Tree problem more efficiently.
Atomic Posts
15 Aug 2026
I’m using the term atomic post in reference to the concept of atomic habits. The idea is for posts to be as narrow as possible in scope, while still being self-contained.
Visit archive to see all posts...