Understanding Communication Complexity & Streaming Algorithms Under Minimal Assumptions 🔍

Moni Naor (Weizmann Institute of Science) https://simons.berkeley.edu/talks/moni-naor-weizmann-institute-science-2023-05-03 Minimal Complexity Assumptions for Cryptography Can computational limitations help improve algorithms? In this talk I will give a few examples where assuming computational limitations on the adversary and particular cryptographic tools allows us to bypass some well known impossibility results in communication complexity and streaming. We will discuss whether we can show that these tools are necessary for the results as well as some open problems. Based on joint works with Boaz Menuhin and Shahar Cohen.