noc21-cs53-Lec17

Name: noc21-cs53-Lec17
Uploaded: 2023-12-04T03:53:30.407Z
Duration: 54 min 6 s
Channel: IIT Kanpur July 201
Description: "Description: In this lecture, we revisit the definition of Prgs. We introduce the notion of S-prgs and show how to deradnomize complexity classes using explicit S-prgs. Finally, we introduce different hardness notions in complexity, namely average-case hardness and worst-case hardness. "

IIT Kanpur July 201

Dec 4, 2023

"Description: In this lecture, we revisit the definition of Prgs. We introduce the notion of S-prgs and show how to deradnomize complexity classes using explicit S-prgs. Finally, we introduce different hardness notions in complexity, namely average-case hardness and worst-case hardness.
"