Association for Computing Machinery (ACM) Courses

Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

Explore unexpected findings on Kolmogorov complexity, including hardness results, limits, conjectures, and implications for pseudorandom generators and computational complexity.

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

Constant Girth Approximation for Directed Graphs in Subquadratic Time

Explore subquadratic-time algorithms for approximating constant girth in directed graphs, covering ball growing techniques, random sampling, and combined approaches for efficient graph analysis.

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

One-Shot Signatures and Applications to Hybrid Quantum-Classical Authentication

Explore quantum-classical hybrid authentication, including one-shot signatures, chameleon hashing, and innovative applications in cryptocurrency and quantum proofs.

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

Faster Energy Maximization for Faster Maximum Flow

Explore advanced techniques for solving maximum flow problems in undirected graphs, focusing on energy maximization and weight reduction strategies to improve algorithmic efficiency.

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

XOR Lemmas for Resilient Functions Against Polynomials

Explore XOR Lemmas for resilient functions against polynomials, including new structural results and correlation bounds for low-degree polynomials.

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

Interactive Shallow Clifford Circuits- Quantum Advantage Against NC and Beyond

Explore quantum advantage in interactive shallow Clifford circuits, examining their superiority over classical NC¹ computations and beyond through innovative problem-solving approaches.

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

Exploration with Limited Memory - Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits

Explore streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits, focusing on limited memory scenarios and efficient problem-solving techniques.

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

Approximating Text-to-Pattern Hamming Distances

Explore efficient algorithms for approximating Hamming distances between text and pattern strings, focusing on structured and combined sampling techniques.

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

Private Stochastic Convex Optimization: Optimal Rates in Linear Time

Explore optimal rates and linear time solutions for private stochastic convex optimization, focusing on empirical risk minimization and privacy amplification techniques.

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

Faster Parallel Algorithm for Approximate Shortest Path

Explore advanced techniques for optimizing parallel algorithms to compute approximate shortest paths, focusing on transshipment, Sherman's framework, and oblivious routing.

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

Contention Resolution without Collision Detection

Explore contention resolution algorithms without collision detection for shared channels, focusing on backoff strategies, channel simulation, and handling player arrivals and stragglers.

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

Postquantum Zero-Knowledge in Constant Rounds

Explore postquantum zero-knowledge protocols with constant rounds, focusing on extractable commitments and quantum-resistant techniques for secure cryptographic systems.

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

Separations and Equivalences Between Turnstile Streaming and Linear Sketching

Explore streaming algorithms, linear sketching, and their equivalences. Learn about turnstile streaming, limitations, and separations in bounded-degree triangle counting and insertion-only algorithms.

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

Approximately Stable Committee Selection

Explore committee selection methods, focusing on fairness, stability, and approximation algorithms. Learn about preference models, participatory budgeting, and innovative approaches to achieve balanced representation.

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

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games

Explore advanced cutting plane methods for convex optimization and games, covering improved algorithms, runtime bottlenecks, data structures, and practical applications in computational mathematics.

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