A brief overview of the 2021 Abel Prize Laureates’ work

A brief overview of the 2021 Abel Prize Laureates’ Avi Wigderson and László Lovász work by Alex Bellos. Alex Bellos is a British writer, broadcaster and populariser of mathematics. This clip is from the 2021 Abel Prize announcement.

Illustrations by Edmund O. Harriss.

[theadityatamar]

The Zero Knowledge Proof is one of the most mind-boggling things that I have ever heard.

[anarcho.pacifist]

Another example for a zero-knowledge proof, is the factorization of large integers. If I have an algorithm that can factorize any 500-digit number into primes in a few seconds, I can prove this to you without revealing my algorithm: you simply give me a 500-digit (random) integer and I will send you back the prime factorization. You can then check in polynomial time that the factorization is indeed correct. Therefore, I probably have a fast integer factorization algorithm. To remove any doubt, we can repeat this process multiple times. As the number of times we repeat this process increases, you become more and more certain that my claim is correct. However, you still don't know my algorithm.

[andraspongracz]

I think you meant NP-hard or NP-complete problems in certain occasions when you said NP-problems.

[vesuviusmount]

A weakness of the map proof is that it's not too hard to fool the checker, even if a 3-colouring doesn't exist.

Take the map of the US. You can colour it with 3 colours, and *almost* every border still looks like a true 3-colouring. If you pick the "matching" border at random and then 3-colour the rest, then the prob of being caught out at each step is not high.

Of course this doesn't invalidate the zero-knowledge proof. But it does make me wonder if proofs exist which are also perfectly mimicable (i.e. observer is fooled with prob 1), and if so whether they can really be called proofs in that case!

[giovanimarin]

Theoretical computer science is mathematics?

[JohnJDMunn]

Selfish and unsolicited suggestion - please put your autocue above your camera, it is very distracting and disconcerting when you look away so often