Wednesday / CS Seminar

February 1st / 10:00 AM

Hybrid / Mudd 3514

Title: A new approach for simulating randomness in computation, and resulting directions of research

Speaker: Roei Tell

Zoom Link

Livestream

Abstract:

Randomness is used throughout computer science, but when does it actually make computation more efficient? A central area in theoretical computer science studies the value of randomness for solving various types of 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 using pseudorandom 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 at *no observable cost* (under suitable assumptions), avoiding overheads that are inherent to classical pseudorandom generators.

2. Strengthening certain connections 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 new results and methods of mine on a main current frontier in this area: Proving better limitations for simplistic models of shallow neural networks, called threshold circuits.

Biography:

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 prior to that he was a postdoc at MIT. He completed his PhD and MSc at the Weizmann Institute of Science, following undergraduate studies in psychology, math, and computer science.