Simons Institute Courses

Local Algorithms: Principles and Applications

Explore insights from Tal Herman's presentation at the Workshop on Local Algorithms, delving into cutting-edge research in computer science and mathematics.

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

Privately Evaluating Untrusted Black-Box Functions

Explore tools for sharing sensitive data with untrusted analysts, focusing on differentially private algorithms and privacy wrappers for black-box functions on datasets.

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

O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set

Explore optimal passes for semi-streaming maximal independent set, focusing on O(log log n) algorithm and new lower bound proof using extremal graphs and round elimination techniques.

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

On the Instance Optimality of Detecting Collisions and Subgraphs

Explore instance optimality in detecting collisions and subgraphs, examining how structural knowledge impacts algorithm efficiency for various detection tasks in functions and graphs.

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

Distribution Learning Meets Graph Structure Sampling

Explore the connection between PAC-learning of graphical models and efficient graph structure sampling, leveraging online learning algorithms for new insights in high-dimensional distribution learning.

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

Verifiable Data Science via Interactive Proofs

Explore interactive proofs for verifiable data science, enhancing trust and reliability in scientific computations and analyses.

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

The Long Path to Square Root of d Monotonicity Testers

Explore directed isoperimetry and its application to monotonicity testing, analyzing directed random walks on product domains for optimal testers in Boolean functions on hypergrids.

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

Property Testing with Incomplete or Manipulated Inputs

Explore property testing with adversarial input manipulation, examining complexity and relationships to offline models. Learn fundamental computational tasks in this challenging scenario.

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

Subgraph Counting and Seed Counting in Graph Theory

Explore sublinear subgraph counting and sampling techniques, focusing on the advantages of counting seeds in graph analysis.

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

Monotonicity Testing, Routing, and the Lehman-Ron Theorem on Hypercube Properties

Explore connections between monotonicity testing, routing on hypercubes, and Lehman-Ron theorem. Gain insights into efficient property testers and low-congestion flows on directed hypercubes.

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

Testing Intersectingness of Uniform Families - How Dana and I Intersected

Explore efficient algorithms for testing intersecting k-uniform set families, including tolerant and one-sided error non-adaptive methods. Compare results to non-uniform families and discover optimal query complexities.

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

Recent Developments in Testing Bounded-Degree Graphs

Explore recent advancements in testing bounded-degree graphs, including locally-characterized expander graphs, graph isomorphism studies, and applications of robustly self-ordered graphs.

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

Challenges in Making Large Language Models Safe and Robust

Explore root causes of safety concerns and attacks on LLMs, evaluate defense strategies, and examine broader implications for machine learning safety and robustness.

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

Graph Connectivity Using Star Contraction

Explore edge connectivity in simple graphs using cut queries, introducing star contraction for efficient graph simplification and discussing randomized and quantum algorithms for connectivity determination.

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

Parallel Algorithms for Local Problems in Sparse Graphs

Explore efficient parallel algorithms for locally checkable problems in sparse graphs, focusing on techniques beyond graph sparsification for improved performance in sublinear regimes.

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