Sublinear Algorithms Courses and Certifications

Simons Institute

Adaptive Sparse Recovery with Limited Adaptivity

Explore techniques for efficient sparse signal recovery using limited adaptive measurements, with applications in sublinear algorithms and nearest-neighbor search.

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

IEEE

Sublinear Algorithms for Gap Edit Distance

Explore sublinear algorithms for efficiently computing gap edit distance, including dynamic programming, approximation techniques, and key theoretical results.

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

Simons Institute

Counting Subgraphs in Sublinear Time

Explore key randomization techniques for estimating subgraph counts without reading entire graphs, focusing on average degree and triangle count estimation methods.

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

Simons Institute

Testing Boolean Functions

Explore efficient algorithms for testing Boolean function properties, covering definitions, variants, and key analyses in sublinear complexity.

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

Simons Institute

Sampling Big Ideas in Sublinear Algorithms

Explore random sampling techniques for enhancing data analysis scalability, focusing on weighted and coordinated sampling schemes for streamed or distributed data.

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

Churchill CompSci Talks

Sublinear Time Property Testers - Algorithms for Efficient Function Analysis

Explore sublinear time property testers for efficient algorithm design. Learn about relaxed decision problems, fast testers, and applications in graph theory and string processing.

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

TheIACR

Sublinear Zero Knowledge Arguments for RAM Programs

Explore cutting-edge cryptographic techniques for efficient zero-knowledge proofs in RAM programs, enhancing privacy and security in computational systems.

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

Simons Institute

Streaming Algorithms for Connectivity Augmentation

Explore cutting-edge streaming algorithms for enhancing network connectivity, focusing on sublinear approaches and their applications in graph theory and data structures.

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

Simons Institute

Hypothesis Selection with Computational Constraints

Explore optimal tradeoffs between memory, sample complexity, and time in hypothesis selection algorithms for distribution matching, with focus on achieving near-optimal accuracy efficiently.

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

Simons Institute

Sublinear Algorithms in Social Networks via Core-Periphery Decomposition

Explore sublinear algorithms for large networks using core-periphery structure and degree distribution. Learn about accelerating tasks like node sampling and shortest path computations.

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

Simons Institute

Linear and Sublinear Algorithms for Graphlet Sampling

Explore efficient algorithms for graphlet sampling, including linear and sublinear preprocessing techniques, with applications to semi-streaming and MPC settings.

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

Simons Institute

Sublinear Insights: A Faster Classical Algorithm for Edge Coloring

Explores a novel randomized algorithm for near-linear time graph edge coloring, improving on decades-old methods. Discusses implications for Vizing's theorem and dense graph coloring efficiency.

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

Simons Institute

Long-context Attention in Near-Linear Time

Explores HyperAttention, an innovative approach to tackle computational challenges in long-context LLMs, offering significant speed improvements while maintaining performance across various datasets.

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

Simons Institute

Randomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomposition

Explore randomized least squares optimization techniques for large-scale tensor decomposition, focusing on sublinear algorithms and their applications in data analysis.

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

Simons Institute

Locally Private Histograms in All Privacy Regimes

Explore frequency estimation in data analysis, focusing on local differential privacy. Learn about algorithms, error bounds, and the intriguing low-privacy regime in histogram computation.

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