Po-Shen Loh is a professor at Carnegie Mellon University and a coach for the US Math Olympiad. He is also a social entrepreneur where he has his used his passion and expertise in mathematics in the service of education (expii.com) and epidemiology (novid.org).
In this episode, we discuss the mathematics behind Loh's novel approach to contact tracing in the fight against COVID, which involves a beautiful blend of graph theory and computer science.
Originally published on March 3, 2022 on Youtube: https://youtu.be/8CLxLBMGxLE
Timestamps:
00:00:00 : Introduction
00:01:11 : About Po-Shen Loh
00:03:49 : NOVID app
00:04:47 : Graph theory and quarantining
00:08:39 : Graph adjacency definition for contact tracing
00:16:01 : Six degrees of separation away from anyone?
00:21:13 : Getting the game theory and incentives right
00:30:40 : Conventional approach to contact tracing
00:34:47 : Comparison with big tech
00:39:19 : Neighbor search complexity
00:45:15 : Watts-Strogatz small networks phenomenon
00:48:37 : Storing neighborhood information
00:57:00 : Random hashing to reduce computational burden
01:05:24 : Logarithmic probing of sparsity
01:09:56 : Two math PhDs struggle to do division
01:11:17 : Bitwise-or for union of bounded sets
01:16:21 : Step back and recap
01:26:15 : Tradeoff between number of hash bins and sparsity
01:29:12 : Conclusion

Further reading:
Po-Shen Loh. "Flipping the Perspective in Contact Tracing" https://arxiv.org/abs/2010.03806