Derandomization: A Quick Tutorial
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a comprehensive tutorial on derandomization, focusing on transforming doubly efficient constant-round interactive protocols into NP-type verifiers with similar time complexity. Delve into the construction of NP-type deterministic argument systems for counting satisfying assignments of large formulas under strong hardness assumptions. Examine the use of targeted pseudorandom generators (tarPRGs) in the interactive protocol setting, drawing parallels to the Fiat-Shamir approach. Learn about the application of complexity-theoretic assumptions that don't necessarily imply one-way functions. Gain insights into recent advancements in derandomization techniques and their implications for cryptography and computational complexity theory.
Syllabus
Derandomization: A Quick Tutorial
Taught by
Simons Institute
Related Courses
The Next Generation of InfrastructureDelft University of Technology via edX The Beauty and Joy of Computing - AP® CS Principles Part 2
University of California, Berkeley via edX Advanced Data Structures in Java
University of California, San Diego via Coursera Theory of Computation
Indian Institute of Technology Kanpur via Swayam 离散数学
Shanghai Jiao Tong University via Coursera