COLLOQUIUM AT BAR-ILAN UNIV. COMPUTER SCIENCE DEPART. - NOAM MAZOR - Thursday, January 23rd 2025 at 12:00 - AUDITORIUM
WHO: Dr. Noam Mazor, Tel Aviv University & Cornell Tech
WHEN: Thursday, January 23rd 2025 at 12:00
WHERE: BUILDING 503 (Computer Science) AUDITORIUM
Title: Computational Analogs of Randomness
Abstract: Computational analogs of information-theoretic notions have given rise to some of the most intriguing phenomena in theoretical computer science. For example, pseudorandomness allows us to bypass Shannon's lower bounds on the key length of encryption schemes. Moreover, computational analogs of entropy and randomness are key tools in the construction of pseudorandom generators and have become foundational concepts in complexity theory and cryptography.
One such computational analog is time-bounded Kolmogorov complexity. This measure lies at the heart of the emerging connections between cryptography and Kolmogorov complexity. Despite its significance, fundamental questions about the hardness of computing this measure remain open. In this talk, we will explore these questions together with recent advancements. We will also discuss how understanding the computational hardness of meta-complexity problems is instrumental in characterizing the existence of cryptographic primitives.
Short Bio: Noam completed his PhD at Tel Aviv University under the supervision of Iftach Haitner. For his PhD work, he received the Blavatnik Prize for Outstanding Israeli PhD Students in Computer Science and the Best Young Researcher Award at TCC 2021. During his PhD, he also received a teaching excellence award at Tel Aviv University. Since then, Noam has been a postdoctoral fellow at Cornell Tech and Tel Aviv University, hosted by Rafael Pass and Joseph Halpern. In 2025, he will join the Cryptography Semester at the Simons Institute as a research fellow. His research focuses primarily on the foundations of cryptography, privacy, and meta-complexity.
