
Understanding Sheaves §3
In a previous post, we discussed sieves, the sievey definition of Grothendieck topologies and a few exaples thereof. Today we’ll return to sheaves, but this time we do so armed with a better understanding of sites (the “places” in which to define sheaves). This post consists of notes and reflections from reading Daniel Rosiak’s book […] Read more

Understanding Sheaves §2
This post is in two parts. The first part consists of notes based on reading Daniel Rosiak’s book Sheaf Theory Through Examples; while the second part of this post (titled “Decompositions as topologies”) consists of new work straight from my notebook. As always the lines are blurred between learning something that is new to me […] Read more

Dynamic programming on nonrecursive structures
In a previous post I mentioned a very simple algorithm for solving decision problems encoded as sheaves on inputs that display some recursive structure. In this post I’ll talk about what goes wrong with that approach when we’re trying to compute on inputs that are presented in a recursive, treelike way and I’ll also propose […] Read more

Understanding sheaves §1
Sheaves came up in my last post, so , since I’m quite new to sheaves, I figured it would be a good idea to learn some more about them. Naturally, I decided to share my notes with you. The books I’m using to learn about sheaves are: (1) Sheaf Theory though Examples [Rosiak] and (2) […] Read more

Compositional algorithms §2: quotienting solution spaces
Last time we spoke a bit about dynamic programming; specifically about solving Weighted Independent Set on trees. You can read about it here. Today things will get a bit more serious. I’ll start by briefly explaining how the algorithm we sketched for trees extends to graphs of bounded treewidth and then I’ll speak about the […] Read more

Categories of temporal graphs §1
Many realworld problems can be formulated and modeled in the language of graph theory. However, realworld networks are often not static. They change over time. These structures are called dynamic or temporal graphs. Here’s an example of temporal star with four leaves; each one of its edges is active twice except for which is active […] Read more