tvd pod

Thomas C. van Dijk
  • 0.0 (0)
  • Education

Thomas van Dijk on algorithms and academia; nuggets, snippets, opinion and interviews.

Episodes

  1. 07/11/2024

    Decision, Optimisation & Construction

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

  2. 07/10/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.

  3. 07/09/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.

  4. 07/08/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.

  5. 07/07/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. 07/06/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.

  7. 07/05/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.

  8. 07/04/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.

  9. 07/03/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!

  10. 07/02/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.

  11. 07/01/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!

  • 11 Episodes

About

Thomas van Dijk on algorithms and academia; nuggets, snippets, opinion and interviews.

Information

  • Creator
    Thomas C. van Dijk
  • Episodes
    11
  • Rating
    Clean
  • Copyright
    © 2022-2026 Thomas C. van Dijk
  • Show Website
    tvd pod