Simons Institute Courses

Communication Complexity, Streaming and Computational Assumptions

Explore how computational limitations and cryptographic tools can bypass impossibility results in communication complexity and streaming, with examples and open problems discussed.

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

New Techniques for Zero-Knowledge- Leveraging Inefficient Provers to Reduce Assumptions

Explores novel approaches in zero-knowledge proofs, focusing on transforming NIZK to ZAPs with inefficient provers. Discusses implications for cryptographic assumptions and fine-grained complexity settings.

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

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness

Explores unstructured hard languages in NP ∩ coNP, providing evidence for their existence and introducing a new NIZK proof construction, advancing understanding of computational complexity and cryptography.

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

Non-Interactive Universal Arguments

Explore the concept of universal arguments and their construction for non-deterministic computations, focusing on recent developments in non-interactive succinct arguments and their universality.

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

Rate-1 BARGs via Fully-Local SSB Hash Families

Explore fully-local SSB hash families and their applications in cryptography, including multi-hop aggregate signatures and incrementally verifiable computation.

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

Correlation Intractability and SNARGs from Sub-exponential DDH

Explore groundbreaking constructions of SNARGs and correlation-intractable hash functions based on sub-exponential DDH, achieving poly-logarithmic proof sizes for Batch-NP and P.

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

Tutorial on Proof Systems

Explore minimal complexity assumptions in cryptography, focusing on proof systems and their applications in secure computation and blockchain technology.

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

Building Human Intelligence at Scale, to Save the Next Generation from ChatGPT

Innovative approaches to scale human intelligence and education in the era of AI, drawing from game theory and real-world problem-solving experiences across mathematics, pandemic control, and live math education.

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

What Do the Theory of Computing and the Movies Have in Common?

Explore the fascinating intersection of theoretical computer science, art, and cinema with Pixar co-founder Alvy Ray Smith, tracing the evolution from pixels to digital movies and its impact on modern computer graphics.

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

A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling

Explores polynomial-time classical algorithm for noisy random circuit sampling, challenging quantum supremacy claims. Discusses computational complexity, experimental implications, and recent progress in quantum computing.

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

Unpacking the Black Box: Regulating Algorithmic Decisions

Explores optimal regulation of prediction algorithms in high-stakes decisions, examining transparency, audits, and targeted tools to address incentive misalignment and improve welfare.

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

Learning to Predict Arbitrary Quantum Processes

Explore quantum learning theory and its surprising ability to predict local properties of arbitrary quantum circuits, contrasting with classical limitations and highlighting potential for efficient quantum dynamics prediction.

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

Learning to Control Safety-Critical Systems

Explore techniques for integrating AI tools in safety-critical systems, focusing on guaranteeing performance, stability, and safety while addressing challenges in networked environments.

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

Generalization and Robustness in Offline Reinforcement Learning

Explore offline reinforcement learning for safety-critical applications, covering generalization, robustness, and imitation learning in large-scale settings with rich function approximation.

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

Mechanism Design with Limited Commitment

Explore dynamic mechanism design with limited commitment, focusing on direct Blackwell mechanisms and their applications in pricing, bargaining, and product personalization.

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