Derandomization Courses and Certifications

Simons Institute

Derandomization: A Quick Tutorial

Explore efficient methods for transforming interactive protocols into NP-type verifiers, using targeted pseudorandom generators and complexity-theoretic assumptions.

• YouTube
• 1 hour 1 minute
• On-Demand
• Free Video

Centre International de Rencontres Mathématiques

Derandomization: Pseudo-randomness from Hardness - Part 1

Explorez la dérandomisation et la pseudo-aléatoire à partir de la difficulté dans cette conférence de Valentine Kabanets, première partie d'un tutoriel sur ce sujet fascinant en mathématiques.

• YouTube
• 1 hour 15 minutes
• On-Demand
• Free Video

Centre International de Rencontres Mathématiques

Derandomization and Meta-complexity - Part 2

Explorez la derandomisation et la méta-complexité dans cette conférence approfondie de Valentine Kabanets, enregistrée lors d'une rencontre thématique au CIRM à Marseille.

• YouTube
• 1 hour 8 minutes
• On-Demand
• Free Video

IIT Kanpur;  NPTEL

Randomized Methods in Complexity

Explore randomized algorithms, complexity theory, and derandomization techniques. Learn about expander graphs, pseudo-random generators, and error-correcting codes in computational complexity.

• Swayam
• 12 weeks
• On-Demand
• Free Online Course

IEEE

High-Precision Estimation of Random Walks in Small Space

Explore advanced techniques for estimating random walks in limited space, covering pseudorandom generators, graph algorithms, and Laplacian systems for efficient problem-solving.

• YouTube
• 25 minutes
• On-Demand
• Conference Talk

IEEE

Nearly Optimal Pseudorandomness From Hardness

Explore cutting-edge pseudorandomness techniques derived from computational hardness, focusing on novel approaches using codes with large alphabets and pseudoentropy extraction.

• YouTube
• 26 minutes
• On-Demand
• Conference Talk

IEEE

Polynomial Data Structure Lower Bounds in the Group Model

Explore polynomial data structure lower bounds in the group model, covering static structures, lower bounds, models, and efficiency concepts. Insights on k-wise independence and derandomization.

• YouTube
• 25 minutes
• On-Demand
• Conference Talk

IEEE

Deterministic Distributed Expander Decomposition Routing with Applications in Distributed Derandomization

Explore deterministic distributed algorithms for expander decompositions and routing, with applications in derandomization. Learn about balanced sparse cut algorithms and recursive techniques.

• YouTube
• 23 minutes
• On-Demand
• Conference Talk

IEEE

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

Explore groundbreaking research on circuit complexity theory, focusing on the connection between derandomization techniques and establishing lower bounds for circuit sizes across various computational models.

• YouTube
• 24 minutes
• On-Demand
• Free Video

IEEE

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

Explore connections between computational complexity theories, focusing on exponential-time hypotheses, derandomization techniques, and circuit lower bounds in theoretical computer science.

• YouTube
• 21 minutes
• On-Demand
• Free Video

Association for Computing Machinery (ACM)

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Explore circuit lower bounds and derandomization, focusing on AC circuits, algorithmic methods, and pseudorandom generators. Learn about recent developments in average-case circuit analysis.

• YouTube
• 21 minutes
• On-Demand
• Free Video

Institute for Advanced Study

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen

Explore advanced topics in computational complexity, including circuit lower bounds, derandomization, and their connections. Gain insights into cutting-edge research and theoretical developments in computer science.

• YouTube
• 1 hour 7 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit

Explore derandomization techniques using expander graphs to reduce error in randomized algorithms without significantly increasing random bits used.

• YouTube
• 23 minutes
• On-Demand
• Free Video

TheIACR

A Note on Perfect Correctness by Derandomization

Explore derandomization techniques for achieving perfect correctness in cryptographic schemes, focusing on public-key encryption and the concept of cryptographic strings.

• YouTube
• 22 minutes
• On-Demand
• Conference Talk

Simons Institute

Coding Theory in Almost Linear Time and Sublinear Space

Explore efficient error-correcting codes with near-linear time and sub-linear space encoding/decoding algorithms. Learn about innovative techniques in hashing, locally correctable codes, and derandomization.

• YouTube
• 44 minutes
• On-Demand
• Free Video