In a previous post I talk about how NP-hardness doesn’t necessarily mean you can’t solve a problem. There are degrees to which this is true or not in practice, but there is also a distinction we can make at the level of complexity theory. Consider the KNAPSACK problem with $n$ items and maximum weight $W$. There is a famous dynamic program for this with runtime order of $n\cdot W$. That looks polynomial, isn’t Knapsack NP-hard?…

Now there’s this funny type of project, right, where somebody does computation with something that’s not “for” computing. Using marbles in some kind of pachinko rig to add binary numbers. Pinging slow servers to temporarily store data.1 I guess redstone in Minecraft kind of is for making circuits, but people have built like … Turing machines and that’s funny. It’s all a bit janky and there’s an absurdist humour to it: these are high-effort shitposts.…

Now today I’d like to talk about a bit of a pet peeve of mine and I guess it’s maybe more of an opinion than usual, or at least it’s something stylistic: how to describe a dynamic program. Sometimes people immediately come at you with a table and how you would loop over it; where to look and what to write – and, I mean, it’s not wrong. If you describe this well, I’ll understand it.…

Now there are all kinds of so-called “meta-theorems” that connect logic and graph algorithms. Here’s a pretty cool one using a logic you may not have heard of: the monadic second-order logic of graphs. You see, Courcelle’s theorem says that for graphs of bounded treewidth, properties definable in this “MSO” logic can be decided in linear time. This makes the graph problem fixed parameter tractable parameterized by treewidth. The proof involves some fairly heavy machinery (or at least terminology I’m not super familiar with) so I personally find the primary literature quite hard to follow and you do have to be a little bit careful what the exact conditions are if you’re going to use it for real, but you know the drill: look it up.…

Now in my first journal paper (and this is back when you would get author’s copies, I still have a stack of like 20 of these; you could send them to colleagues, I guess) the plots were EPS exported from Excel. While it was an upgrade from the screenshots I took for my thesis, it doesn’t look great either way. So how do you make plots and graphics for your papers?…