Simons Institute Courses

Batch Proofs Are Statistically Hiding

Explore statistical hiding in batch proofs, examining implications for cryptographic assumptions and protocols. Insights on statistical soundness, computational soundness, and non-interactive batch arguments.

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

Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography

Explore proof systems and their implications for information-theoretic cryptography, examining the impossibility of efficient solutions for key tasks in the field.

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

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE

Explores innovative cryptographic solutions for private internet searches, combining efficient data structures with Ring LWE-based encryption to enable secure, scalable information retrieval.

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

Optimization: Higher-order Methods - Part 2

Explore advanced optimization techniques and higher-order methods for fast algorithms, focusing on data structures and their applications in algorithmic efficiency.

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

Optimization: Higher-order Methods - Part 1

Explore advanced optimization techniques using higher-order methods, focusing on theoretical foundations and practical applications in algorithm design and data structures.

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

Optimization: First-order Methods - Part 2

Explore advanced first-order optimization techniques, focusing on accelerated gradient methods and their applications in solving complex algorithmic problems.

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

Optimization: First-order Methods - Part 1

Explore first-order optimization methods with Alina Ene, focusing on fundamental techniques and algorithms for efficient problem-solving in data structures and algorithm design.

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

Optimization: Interior Point Methods - Part 2

Explore advanced interior point methods for optimization, focusing on data structures and algorithms to enhance computational efficiency in solving complex problems.

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

Optimization: Interior Point Methods - Part 1

Explore interior point methods for optimization with Stanford's Yinyu Ye, covering fundamental concepts and applications in data structures and fast algorithms.

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

Matrix Data Structures

Explore efficient matrix data structures for fast algorithms, focusing on optimization techniques and their applications in computational mathematics.

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

Introduction to Data Structures and Optimization for Fast Algorithms

Explore essential data structures and optimization techniques for designing efficient algorithms, enhancing problem-solving skills in computer science and software engineering.

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

Dynamic PageRank: Additive Error and Batch Recomputation

Explores dynamic PageRank algorithms, proving hardness of relative error approximations and demonstrating efficiency of batch recomputation for L1 error metric in dynamic graph settings.

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

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates

Explore dynamic algorithms for packing-covering LPs using multiplicative weight updates, focusing on near-optimal approximation algorithms and complexity analysis in dynamic settings.

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

Online List Labeling - Breaking the Log^2 N Barrier

Explores a randomized data structure for online list labeling, improving the upper bound to O(log^{3/2} n) items moved per insertion/deletion, breaking the long-standing log^2 n barrier.

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

Practical Dynamic Graph Algorithms - Data Structures and Connections Between Models

Explore efficient data structures and techniques for dynamic graph algorithms across multiple computational models, focusing on k-core decomposition, densest subgraph, and triangle counting problems.

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