Constant-Cost Communication in Randomized Computing

Watch a mathematics lecture exploring the power of randomness in communication complexity, focusing on scenarios where shared randomness enables two parties to solve complex problems with minimal communication costs. Delve into the Equality problem, where determining if two n-bit strings are identical traditionally requires n bits of deterministic communication but can be solved with just 2 bits using randomized protocols. Examine the characteristics of communication problems that allow for such efficient randomized solutions and investigate the structural properties of their corresponding Boolean matrices. Learn about recent developments and ongoing challenges in this field through research conducted in collaboration with Yuting Fang, Mika Göös, Lianna Hambardzumyan, Nathaniel Harms, and Hamed Hatami.