tvd pod
Activity Overview
Episode publication activity over the past year
Episodes
SQL can do more than you remember
Contributed by Lukas
If you study computer science, you take a databases class. I guess there are trends and there are different ways to focus it, but still everybody lear...
The "Intermediate Value Theorem"
Contributed by Lukas
As theorems go, the Intermediate Value Theorem is pretty obvious, especially if you don't try to generalize it. But asw a tactical move, it is useful ...
Total Unimodularity
Contributed by Lukas
There is a property of matrices called “unimodularity” and a variant I want to talk about today called total unimodularity. The definition is a bi...
Decision, Optimisation & Construction
Contributed by Lukas
When we talk about an optimisation problem, there are actually different variants that we’re not usually explicit about: decision, optimisation, and...
Existential Theory of the Reals
Contributed by Lukas
More pedantry about NP-hardness! We have already seen a version of the SUM OF RADICALS problem, where it turned out comparing sums of square roots is ...
The "Sum of Radicals" problem
Contributed by Lukas
We have talked about "reasonable encodings" of integers, and why that matters, but what about real numbers? You could give a finite expansion, that is...
Binary Encoding for Arbitrarily Large Integers
Contributed by Lukas
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 yo...
NP-hardness and "reasonable encodings"
Contributed by Lukas
NP-hardness is about Turing machines. It’s about symbols on tapes, and state transitions, and moving heads. There are shortcuts to thinking about th...
PP is Overpowered
Contributed by Lukas
There are all kinds of different complexity classes for probabilistic computation. We'll get into some reasonable ones another time, but here's one th...
NP-hard doesn't mean you can't solve it
Contributed by Lukas
NP-hard problems often get talked about is as if you can't solve them. Well, probably not in worst-case polynomial time on a deterministic Turing mach...
Can't look it up if you've never heard of it.
Contributed by Lukas
Sometimes the most important thing is having heard of something - because you can't look it up if you've never heard of it. In this series of videos, ...