Association for Computing Machinery (ACM) Courses

Nearly Optimal Static Las Vegas Succinct Dictionary

Explore advanced data structures for efficient dictionary operations, focusing on succinct representations and optimizing space usage for various input types.

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

Weighted Min-Cut - Sequential, Cut-Query and Streaming Algorithms

Explore advanced algorithms for solving the weighted min-cut problem across sequential, cut-query, and streaming models, with a focus on a unified schematic approach and open challenges.

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

Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators

Explore efficient parallel algorithms for approximating undirected shortest paths using low hop emulators, with applications and open problems in graph theory and network analysis.

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

Non-Adaptive Adaptive Sampling on Turnstile Streams

Explore non-adaptive adaptive sampling techniques for turnstile streams, covering data summarization, streaming algorithms, and applications in subset selection, subspace approximation, and volume maximization.

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

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Explore circuit lower bounds and derandomization, focusing on AC circuits, algorithmic methods, and pseudorandom generators. Learn about recent developments in average-case circuit analysis.

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

A Lower Bound for Parallel Submodular Minimization

Explore lower bounds for parallel submodular minimization, examining adaptive complexity models and exponentially faster algorithms for this optimization problem.

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

Towards a Better Understanding of Randomized Greedy Matching

Explores randomized greedy matching algorithms, introducing Modified Randomized Greedy (MRG) and analyzing its performance in various graph scenarios, including weighted and oblivious matching.

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

Breaching the 2-Approximation Barrier for Connectivity Augmentation

Explore advanced techniques in network design, focusing on connectivity augmentation and its reduction to the Steiner Tree problem. Learn about novel approximation algorithms and open challenges in the field.

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

Catalytic Approaches to the Tree Evaluation Problem

Explore catalytic approaches to the Tree Evaluation Problem, including pebbling games and catalytic space. Learn about multiplication lemmas and formulas for TEP.

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

Strong Self-Concordance and Sampling

Explore an algorithm for efficient polytope sampling, its connection to the KLS conjecture, and the properties of strong self-concordance in barrier functions.

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

Automating Cutting Planes is NP-Hard

Explore the complexity of automating cutting planes in computational geometry, covering historical context, algorithmic challenges, and proof systems.

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

Rounding Dynamic Matchings Against an Adaptive Adversary

Explore dynamic matching algorithms against adaptive adversaries, covering sparsifiers, fractional matching, and edge coloring to improve computational efficiency in graph theory.

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

Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity

Explore quantum vs. classical communication complexity, focusing on interactive and simultaneous message passing models, bit/qubit complexities, and the Gap Hamming Relation.

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

Quadratic Speedup for Finding Marked Vertices by Quantum Walks

Explore quantum walks for efficient vertex search, offering quadratic speedup over classical methods. Learn about structured search, constraints, and applications in quantum computing.

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

Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths

Explore efficient algorithms for constructing directed hopsets and parallel approximate shortest paths, enhancing graph analysis and routing applications.

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