When we talk about an optimisation problem, there are actually different variants that we’re not usually explicit about: decision, optimisation, and construction. We don’t usually care that much about this distinction - it’s just that algorithms usually solve the construction version and complexity theory is usually about the decision version, where we don’t mind because typically it’s all polynomially related. But we can still be smart about it...
10 Jul 2024
Existential Theory of the Reals
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 tricky. But irrational numbers are kind of wild, right, so maybe we don't really need to care? Surprise: geometry! Euclidean distance has square roots so this is kind of a big deal, actually, and it bites both ways for NP-completeness.
9 Jul 2024
The "Sum of Radicals" problem
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 fine, or use rational numbers - though in either case you might have to be a little bit careful about how large your representation is and if you can actually work with that representation efficiently. Queue the Sum of Radicals problem.
8 Jul 2024
Binary Encoding for Arbitrarily Large Integers
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.
7 Jul 2024
Total Unimodularity
There is 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. That may not be the most intuitive thing, but it turns out totally unimodular matrices have some algorithmically useful properties.
6 Jul 2024
The "Intermediate Value Theorem"
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 to be aware of.
5 Jul 2024
NP-hardness and "reasonable encodings"
NP-hardness is about Turing machines. It’s about symbols on tapes, and state transitions, and moving heads. 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 leaks out of the definition: so-called reasonable encodings.
4 Jul 2024
PP is Overpowered
There are all kinds of different complexity classes for probabilistic computation. We'll get into some reasonable ones another time, but here's one that sounds like a good idea, maybe, but is really powerful in a way that's just not reasonable.
3 Jul 2024
SQL can do more than you remember
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 learns SQL. Maybe you’ll say “oh of course, didn’t you know that?” But here are some things that I didn’t know until fairly recently. If there is a thing you wish you were allowed to write, maybe you actually are!
2 Jul 2024
NP-hard doesn't mean you can't solve it
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 machine: sure. But exponential time is not forbidden, it's just a lot. Computers are pretty fast though and sometimes the instances that you want to solve aren't that large anyway. Depending on both the problem and the methods, you can solve larger instances than you might expect.
1 Jul 2024
Can't look it up if you've never heard of it.
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, I discuss computer science, maths and GIS topics that I think are cool, and that you might enjoy having heard of. And maybe you'll use some of this one day!
Contact tvd pod
Guest appearances
Does not typically book guests
Based on episode analysis; this does not confirm that the show is currently accepting guests.
Host of tvd pod?
Claim your podcast to manage its listing and keep your show details accurate.
Pod Engine is an independent podcast discovery and analytics service and is not affiliated with or endorsed by this podcast. Artwork and show content belong to their owners. Full legal notice.
Explore this show Podcast research with Pod Engine
