Understanding Communication Complexity & Streaming Algorithms Under Minimal Assumptions π
Explore Moni Naor's insights on the foundational aspects of communication complexity, streaming algorithms, and the computational assumptions that underpin modern computer science. Dive into minimal complexity assumptions and their impact on theory and pr
Simons Institute for the Theory of Computing
474 views β’ May 4, 2023
About this video
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.
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.
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
474
Likes
6
Duration
01:01:21
Published
May 4, 2023
Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.
Trending Now