Communication Complexity, Streaming and Computational Assumptions

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=Yr8AOzlJYC8


Duration: 1:01:21
425 views
3

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.



Other Videos By Simons Institute for the Theory of Computing


2023-05-05Unclonable Polymers and Their Cryptographic Applications
2023-05-05Batch Proofs are Statistically Hiding
2023-05-05Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
2023-05-04Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
2023-05-04Assumptions in cryptography and complexity theory
2023-05-04Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization
2023-05-04Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
2023-05-04Tutorial on obfuscation
2023-05-04Fine-Grained Cryptography
2023-05-04On the Complexity of Two-Party Differential Privacy
2023-05-03Communication Complexity, Streaming and Computational Assumptions
2023-05-03NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
2023-05-03Capturing One-Way Functions via NP-Hardness of Meta-Complexity
2023-05-03Derandomization: A Quick Tutorial
2023-05-03SNARGs Beyond Non-Signaling
2023-05-03Cryptographic Hardness of Correlated Sampling
2023-05-03Incompressiblity and Next-Block Pseudoentropy
2023-05-02Cryptography and Kolmogorov Complexity: A Quick Tutorial
2023-05-02Constant-Round Arguments from One-Way Functions
2023-05-02New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...
2023-05-02Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Minimal Complexity Assumptions for Cryptography
Moni Naor