Sublinear Algorithms Courses and Certifications

Simons Institute

Coresets and Their Applications to Design Sublinear Algorithms

Explore coresets and their role in designing efficient sublinear algorithms, enhancing computational performance for large-scale data analysis and machine learning tasks.

• YouTube
• 52 minutes
• On-Demand
• Free Online Course

Simons Institute

Sublinear Time Algorithms for Estimating Edit Distance

Explore efficient methods for approximating edit distance between strings, focusing on sublinear time algorithms and their applications in computational biology and text processing.

• YouTube
• 1 hour 8 minutes
• On-Demand
• Free Online Course

Simons Institute

Extroverted Sublinear Algorithms

Explore extroverted sublinear algorithms with Google Brain researcher Ilya Mironov, delving into innovative computational techniques for efficient data processing and analysis.

• YouTube
• 25 minutes
• On-Demand
• Free Online Course

Simons Institute

Sublinear Time Algorithms for Max-Cut Approximation on Expander Graphs

Explore random walks on graphs to achieve better-than-1/2 approximation for max-cut on expanding and clusterable graphs, using sublinear time algorithms.

• YouTube
• 32 minutes
• On-Demand
• Free Online Course

Simons Institute

Efficiently Computing Similarities to Private Datasets

Explore advanced techniques for computing similarities to private datasets, focusing on extroverted sublinear algorithms and their applications in data privacy.

• YouTube
• 30 minutes
• On-Demand
• Free Online Course

Simons Institute

O(log s)-Approximate Nearest Neighbor Search for Earth Mover's Distance

Explore advancements in nearest neighbor search for Earth Mover's Distance, improving approximation to Õ(log s) with sublinear query time using data-dependent LSH functions and tree embedding techniques.

• YouTube
• 37 minutes
• On-Demand
• Free Online Course

Simons Institute

Shaving Logs by Weighing Coins - Extroverted Sublinear Algorithms

Explore innovative sublinear algorithms for efficient data analysis, focusing on log-shaving techniques and coin-weighing problems in computational complexity.

• YouTube
• 39 minutes
• On-Demand
• Free Online Course

Simons Institute

New Upper and Lower Bounds on Approximate Counting

Explores new upper and lower bounds for approximate counting, addressing amortized space complexity and memory optimization in maintaining arrays of approximate counters.

• YouTube
• 48 minutes
• On-Demand
• Free Online Course

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

High Dimensional Robust Sparse Regression

Explore advanced techniques for robust sparse regression in high-dimensional data, focusing on sublinear algorithms and nearest-neighbor search methods.

• YouTube
• 45 minutes
• On-Demand
• Free Online Course

Simons Institute

Learning-Augmented Sketches for Frequency Estimation

Explore advanced techniques for frequency estimation using learning-augmented sketches, enhancing sublinear algorithms and nearest-neighbor search methodologies.

• YouTube
• 46 minutes
• On-Demand
• Free Online Course

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 Online Course

Association for Computing Machinery (ACM)

Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

Explore quantum-inspired classical algorithms for machine learning, focusing on sublinear low-rank matrix arithmetic and singular value transformation techniques.

• YouTube
• 21 minutes
• On-Demand
• Free Online Course

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

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 Online Course