News & Events

Department Events & Announcements

Events

• Feb

  1

  CS Seminar: A new approach for simulating randomness in computation, and resulting directions of research (Roei Tell)

  Department of Computer Science (CS)

  10:00 AM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

  EVENT DETAILS

  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.

  more less

  TIME Wednesday, February 1, 2023 at 10:00 AM - 11:00 AM

  LOCATION 3514, Mudd Hall ( formerly Seeley G. Mudd Library)    map it

  ADD TO CALENDAR

  CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

  CALENDAR Department of Computer Science (CS)