BEGIN:VCALENDAR
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
UID:20230321T012040-407352859-northwestern.edu
DTSTAMP:20230321T012040
DTSTART:20230201T100000
DTEND:20230201T110000
SUMMARY:CS Seminar: A new approach for simulating randomness in computation, and resulting directions of research (Roei Tell)
LOCATION:3514, Mudd Hall ( formerly Seeley G. Mudd Library)
DESCRIPTION:Wednesday / CS Seminar\nFebruary 1st / 10:00 AM\nHybrid / Mudd 3514\nTitle: A new approach for simulating randomness in computation, and resulting directions of research\nSpeaker: Roei Tell\nZoom Link\nLivestream\nAbstract: \nRandomness 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. \n\nI 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:\n1. 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. \n2. Strengthening certain connections in computer science: Proving that simulating randomness is *equivalent* to solving problems from complexity theory, cryptography, learning theory, and other areas.\nI 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. \n\nBiography:\nRoei 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.\n\nPiP URL: https://planitpurple.northwestern.edu/event/597447
END:VEVENT
END:VCALENDAR
ORGANIZER:Department of Computer Science (CS)