NP-Incompleteness
The Geography Game
14 Sep 2024
In this post we’d like to discuss the Geography game. In the variant we’ll consider, an instance of the game is an undirected graph, and a token placed in one of its vertices.
Two players take turn in moving the token to an adjacent vertex with the constraint that no vertex can be visited twice. If a player cannot move the token without violating that constraint, they lose.
Assuming both players play optimally, it turns out that we can determine which player will win. We’ll also present the optimal strategy each player can use and discuss other variants.
Removable Singularities
31 Aug 2024
This is the 7-th post in the series with my notes on complex integration, corresponding to Chapter 4 in Ahlfors’ Complex Analysis.
In this post we’ll cover Removable Singularities in the context of holomorphic functions.
Coroutines in C++: A Minimal Library
23 Aug 2024
In the previous post we started studying coroutines in C++. One of the main takeaways is that the coroutine API offered by STL is pretty low level and not very useful for end developers.
In this post I’d like to cover the implementation of a minimal library that supports co_await and co_return. It’s a dummy library in the sense that it doesn’t do anything with co_await and treats co_return as return, so it doesn’t add any value compared to non-coroutine code.
The goal however is to understand the necessary machinery that has to happen for this simplest example to work.
Holomorphic Functions are Analytic
02 Jul 2024
This is our sixth post in the series with my notes on complex integration, corresponding to Chapter 4 in Ahlfors’ Complex Analysis.
In this post however, we won’t follow Ahlfors’ book, but rather Terry Tao’s notes on Complex Analysis [2] to show that holomorphic functions are analytic.
Negative Bloom Filters
22 Jun 2024
Recently at work we were trying to solve a performance bottleneck. A part of the system was making requests to a remote key-value store but we saw that the majority of the requests resulted in the key not existing in the store.
An idea was to implement a negative cache: locally store the keys for which no value exist, to prevent unnecessary future requests. It should not use much memory and false negatives are fine (would result in redundancy), but false positives are not allowed (would result in incorrect results).