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
Patreon: https://www.patreon.com/timothynguyen
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