• Understanding Sheaves §3

    In a previous post, we discussed sieves, the sieve-y 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 non-recursive 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, tree-like 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 tree-width and then I’ll speak about the […] Read more

  • Categories of temporal graphs §1

    Many real-world problems can be formulated and modeled in the language of graph theory. However, real-world 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