Now a lot of maths and computer science is about reductions to systems that are somehow restricted and therefore easier to work with, right? Like how any logical formula can be put in conjunctive normal form, or how you can make all logical operators from NAND; how there’s row echelon form for systems of linear equalities and standard form for linear programs. Here’s a fun one that lies at the heart of the simplex algorithm: slack form.…

Now planar graphs have a dual, right? Make a vertex for every face and an edge between them if the two faces are adjacent. (Don’t forget the outer face.) Here’s a fun construction: take a spanning tree $T$ in the original graph and consider those edges impassible for the dual – that is, don’t consider the faces adjacent in the dual if the edge between them is in $T$. Call what remains of the dual graph $D$: I claim $D$ is in fact a spanning tree of the dual.…

Now today, please permit me to rant for a second about connecting the dots when you plot data. Stop it! I mean, probably. Ask yourself: “does it make sense to interpolate these data points?” The answer is probably “no” and you should just do a scatterplot with individual points. There are counterexamples: maybe you plot an ROC curve for a binary classifier. It is literally possible take linear combinations of classifiers to get the interpolated properties.…

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.…