Probabilistically Checkable Proofs Courses and Certifications

Simons Institute

Crash Course on Probabilistically Checkable Proofs - Introduction

Explore probabilistically checkable proofs, including recoloring, constraint satisfaction, and the PCP theorem. Learn about verifier parameters and hardness of approximation in this comprehensive introduction.

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

Simons Institute

Probabilistically Checkable Proofs - Part I

Explore probabilistically checkable proofs, focusing on proof verification, randomized verifiers, and proof rewriting techniques in this advanced theoretical computer science lecture.

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

IEEE

Stoquastic PCP vs. Randomness

Explore the intriguing relationship between stoquastic PCP and randomness in quantum computing, delving into cutting-edge research and its implications for complexity theory.

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

Simons Institute

PCPs and Global Hyper-contractivity - Lecture 3

Explore advanced concepts in PCPs and global hyper-contractivity with Dor Minzer, delving into complex mathematical theories and their applications in analysis and theoretical computer science.

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

Simons Institute

PCPs and Global Hyper-contractivity - Lecture 1

Explore advanced concepts in theoretical computer science, focusing on Probabilistically Checkable Proofs and global hyper-contractivity with expert Dor Minzer.

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

Simons Institute

PCPs and Global Hyper-contractivity - Lecture 1

Explore advanced concepts in theoretical computer science, focusing on Probabilistically Checkable Proofs and global hyper-contractivity with expert Dor Minzer.

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

Institute for Advanced Study

Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders

Delve into probabilistically checkable proofs (PCPs), exploring their encoding, verification, and applications in computer science, with focus on achieving small soundness using high-dimensional expanders.

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

Simons Institute

Crash Course on Probabilistically Checkable Proofs - PCP

Explore probabilistically checkable proofs, their formulation, global vs local tests, and computational implications in this comprehensive lecture on advanced theoretical computer science concepts.

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

Simons Institute

Fully Linear PCPs and Their Cryptographic Applications

Explore probabilistically checkable proofs, distributed verifiers, and cryptographic applications with a focus on fully linear PCPs and their impact on secure protocols and communication complexity.

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

Simons Institute

How to Do Fiat-Shamir in the Standard Model

Explore interactive protocols, Fiat-Shamir transformation, and delegation in cryptography. Learn about security assumptions, hash functions, and correlation intractability in probabilistic proof systems.

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

Simons Institute

How to Delegate Computations Publicly

Explore probabilistically checkable and interactive proof systems, focusing on publicly verifiable arguments and non-interactive protocols for delegating computations.

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

Simons Institute

Transparent SNARKs from DARK Compilers

Explore transparent SNARKs and DARK compilers in cryptography. Learn about polynomial commitments, interactive proof systems, and recent advancements in zero-knowledge proofs for blockchain applications.

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

Simons Institute

Efficient Zero Knowledge Proof from Interactive Proofs

Explore efficient zero-knowledge proofs derived from interactive proofs, focusing on new algorithms, performance improvements, and comparisons to existing systems.

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

Simons Institute

Efficient Zero-Knowledge Proofs: A Modular Approach

Explore modular techniques for creating efficient zero-knowledge proofs, focusing on probabilistically checkable and interactive proof systems in cryptography.

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

Simons Institute

Linearity Testing Over the Biased Cube

Explores linearity testing in p-biased settings, presenting a 4-query test with optimal soundness. Discusses structural results and direct product tests for functions correlated to linear functions under random restrictions.

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