The Taub Faculty of Computer Science Events and Talks

Many interesting questions in coding theory revolve around conflicts (tradeoffs). Among them are a conflict between structure and randomness, and a conflict between density and symmetry. In some of the cases the conflicts are helpful in understanding solutions for questions (e.g. using the structure and randomness conflict we obtain improved analysis of Reed Muller codes), while in other cases these conflicts shed light on the inherent difficulty of the questions. In the talk, I'll explain these conflicts and demonstrate their relations to some important questions in computer science, such as locally testable and correctable codes. The underlining goal is that better understanding of these conflicts will lead to better codes and improved analysis of known codes.