-
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
-
Compositional Algorithms
I’m fascinated by compositionality, the study of how the whole can be determined by its parts. Category theorists will tell you that this topic sits entirely within their domain… and they’re not wrong, but fundamentally I think that most of mathematics has to do with some sort of compositionality. One particular flavor of compositionality that… Read more
-
Hello World
Hi I’m Ben. This is a research blog consisting of notes on the mathematical curiosities that happen to be floating around my mind. If you read anything that appeals to you, leave a comment or get in touch! Read more