noc21-cs53-Lec16

Name: noc21-cs53-Lec16
Uploaded: 2023-12-03T14:16:08.934Z
Duration: 59 min 45 s
Channel: IIT Kanpur July 201
Description: "Description: In this lecture, we first give a non-trivial upper bound on the spectral gap of the Zig-Zag product due to Reingold-Trvisan-Vadhan '05. Finally we derandomize Upath and put it in logspace; this is a famous result by Reingold'05. Towards the end, we introduce an important concept of psuedorandom generators (prgs). "

IIT Kanpur July 201

2 Video Views·Dec 3, 2023

"Description: In this lecture, we first give a non-trivial upper bound on the spectral gap of the Zig-Zag product due to Reingold-Trvisan-Vadhan '05. Finally we derandomize Upath and put it in logspace; this is a famous result by Reingold'05. Towards the end, we introduce an important concept of psuedorandom generators (prgs).
"