Video: 99.9% is easy, 100% is hard

Why is randomness so powerful for algorithms? A Polylog video based on our earlier talk at SNiC.

As usual, things took a bit longer than we expected! Everyone is busy. It also ended up being on the shorter side for Polylog standards, clocking in at 10 minutes. I think it's mostly because we ended up cutting most of the philosophical musings we usually do towards the end of the video. Vašek Rozhoň was not very involved for this one, which probably has something to do with it: he's usually the biggest fan of highlighting broader connections beyond the specific problem we're discussing.

Some of the things that were cut:

• more about polynomial identity testing
• connection to cryptography - the best password is a random one because it's unpredictable
• randomized primality testing and the "recent" deterministic AKS primality test