Communication Complexity, Streaming and Computational Assumptions

Communication Complexity, Streaming and Computational Assumptions

Explore the intersection of computational limitations and algorithmic improvements in this lecture by Moni Naor from the Weizmann Institute of Science. Delve into examples where assuming computational constraints on adversaries and utilizing specific cryptographic tools can overcome established impossibility results in communication complexity and streaming. Examine the potential necessity of these tools for achieving such results and consider open problems in the field. Learn about joint research with Boaz Menuhin and Shahar Cohen, focusing on minimal complexity assumptions for cryptography and their implications for communication complexity and streaming algorithms.