Tight Bounds for General Computation in Noisy Broadcast Networks
Watch a technical lecture exploring the theoretical bounds of computation in noisy broadcast networks, delivered by Dr. Raghuvansh Saxena from TIFR Mumbai. Delve into the challenges of converting protocols for n-party broadcast channels into noise-resilient versions, examining the overhead requirements in terms of communication rounds. Learn about groundbreaking findings that establish tight bounds between Gallager's classical O(log log T) result for non-interactive protocols and the general O(log T) upper bound, revealing a new O(sqrt(log T)) overhead scheme that applies universally. Understand the matching lower bound proof using pointer chasing protocols, demonstrated through rigorous mathematical analysis. Gain insights from Dr. Saxena's expertise in communication complexity, coding theory, and distributed systems, drawing from his research experience at Princeton University and TIFR Mumbai.