(You can watch the video version of this post on YouTube.) Question: How do you efficiently encode an arbitrarily large integer using bits? And to make things interesting, let’s say I can’t see how long your encoding is: I just start reading and that must tell me when I’m done reading; otherwise you could just write it in binary and we’d be done. Being able to see when to stop reading is actually a pretty good property to have, because then the representation composes well.…

(You can watch the video version of this post on YouTube.) Now there’s a property of matrices called “unimodularity” and a variant I want to talk about today called total unimodularity. The definition is a bit opaque: a matrix is totally unimodular if every square submatrix has determinant 0, +1 or −1. It doesn’t really help that I don’t have a great intuition about determinants, but here’s the thing. Let $A$ be a totally unimodular matrix and $b$ an integer.…

(You can watch the video version of this post on YouTube.) Now here’s a theorem that’s fairly obvious? Especially if you don’t try to generalise it, but like, as a tactical move it’s useful to be aware of. As the shape of an argument. So let $f$ be real function that’s continuous on the interval $[a,b]$. Then on this interval it must take ALL values between $f(a)$ and $f(b)$. It’s often used existentially, saying that a particularly function value that we like must be attained.…

(You can watch the video version of this post on YouTube.) One thing I always enjoy pointing out is that NP-hardness … is about Turing machines. It’s about symbols on tapes, and uh, state transitions and moving heads. I mean, there are shortcuts to thinking about this that are basically equivalent in all the ways that we care about, but here’s a formal “implementation detail” – so to speak – that kind of leaks out of the definition.…

(You can watch the video version of this post on YouTube.) Now using matrix multiplication, you can do scaling and rotation around the origin, right? Shearing too. But it’s all around the origin, and there’s no way to do translation .. with just a matrix-vector multiplication. It’d be nice if we could represent any affine transformation by a matrix, and compose them by multiplying the matrices as normal. Enter: homogeneous coordinate.…