Colloquium Details
A new approach for simulating randomness in computation, and resulting directions of research
Speaker: Roei Tell, Institute for Advanced Study
Location: 60 Fifth Avenue 150
Date: February 21, 2023, 2 p.m.
Host: Oded Regev
Synopsis:
Randomness is used throughout computer science, but when does it actually help make computation more efficient? A central area in theoretical computer science studies the value of randomness for solving different types of computational problems, and the ways to simulate true randomness by deterministic algorithms.
I will describe a new algorithmic approach that I introduced for simulating randomness, which avoids the paradigm of using pseudorandom number generators, and instead tailors custom-made pseudorandomness to each individual algorithm. This approach enabled new directions of research that I have been pursuing, and I will mention two of those:
1. Free lunch theorems: Simulating randomness for rich classes of algorithms and protocols at *no observable cost* (under suitable assumptions), avoiding inefficiencies that are inherent to classical pseudorandom generators.
2. Connections between main problems in computer science: Proving that simulating randomness is *equivalent* to solving problems from complexity theory, cryptography, learning theory, and other areas.
I will also present recent progress in circuit complexity, which is a path towards proving that P ≠ NP that is closely connected to simulating randomness. Specifically, I will describe state-of-the-art results of mine on a main current frontier in this area: Proving better limitations for simplistic models of shallow neural networks, called threshold circuits.
Speaker Bio:
Roei Tell is a theoretical computer scientist whose research focuses on randomness in computation, and more broadly on complexity theory. He is currently a postdoc at the Institute for Advanced Study, joint with DIMACS, and simultaneously holds the position of the Richard M. Karp Fellow at the Simons Institute. Prior to that he was a postdoc at MIT, after completing his PhD and MSc in theoretical computer science at the Weizmann Institute of Science. Roei is a recipient of the Rothschild Postdoctoral Fellowship, the John F. Kennedy Prize (highest PhD award at the Weizmann Institute), the Danny Lewin Best Student Paper Award at STOC 2019, and the Shimon Even Prize in Theoretical Computer Science.
Notes:
In-person attendance only available to those with active NYU ID cards.