Raghuvansh Saxena will present his General Exam on Monday, October 16, 2017 in CS 233 at 11am. The members of his committee are: Gillat Kol (adviser), Matt Weinberg, and Mark Braverman. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. "Interactive Coding Over the Noisy Broadcast Channel" A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? This problem was first suggested by El Gamal in 1984. In 1988, Gallager gave an elegant noise-resistant protocol requiring only O(n log log n) rounds. The problem got resolved in 2005 by a seminal paper of Goyal, Kindler, and Saks, proving that Gallager’s protocol is essentially optimal. We revisit the above noisy broadcast problem and show that O(n) rounds suffice. This is possible due to a relaxation of the model assumed by the previous works. We no longer demand that exactly one player broadcasts in every round, but rather allow any number of players to broadcast. However, if it is not the case that exactly one player chooses to broadcast, each of the other players gets an adversely chosen bit. We generalized the above result and initiate the study of interactive coding over the noisy broadcast channel. We show that any interactive protocol that works over the noiseless broadcast channel can be simulated over our restrictive noisy broadcast model with constant blowup of the communication. Reading list: Textbook: Computational Complexity: A Modern Approach - By Sanjeev Arora and Boaz Barak. Survey: Coding for Interactive Communication: A Survey - By Ran Gelles. Papers: Finding parity in a simple broadcast network - Robert Gallager Deterministic coding for interactive communication - Leonard Schulman Communication on noisy channels: a coding theorem for computation - Leonard Schulman Lower Bounds for the Noisy Broadcast Problem - Navin Goyal, Guy Kindler, and Michael Saks Towards Coding for Maximum Errors in Interactive Communication - Mark Braverman and Anup Rao A coding theorem for distributed computation - Sridhar Rajagopalan and Leonard Schulman Information Equals Amortized Communication - Mark Braverman and Anup Rao Interactive channel capacity - Gillat Kol and Ran Raz Constant-rate coding for multiparty interactive communication is impossible - Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings - Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan