Seminars

View all Seminars  |  Download ICal for this event

Hardness vs Randomness in the 2020s

Series: Bangalore Theory Seminars

Speaker: Roei Tell, University of Toronto

Date/Time: May 18 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
The popular approach to hardness vs randomness shifted in the last five years. Instead of starting from circuit lower bounds and building PRGs, many recent works start from hardness assumptions for uniform algorithms, and build objects called targeted PRGs. This shift led to a surprisingly large number of new results and research directions.

In the talk we will first see what exactly is new in this recent approach, and mention some technical tools that have been constructed and are now available off-the-shelf. The main focus will then be applications, ranging across derandomization, explicit constructions, circuit lower bounds, low-space algorithms, arithmetic complexity, and (of course) cryptography -- specifically, a close connection to Fiat-Shamir.


Microsoft Teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan