23:05A Little Clairvoyance Is All You Need
Advanced
A 23-minute video from FOCS 2025: “A Little Clairvoyance Is All You Need”.
79 subscribers on YouTube
Shorts, livestreams, trailers and promos are never listed. Unless a curator approved this channel in full, only individually picked videos appear.
23:05Advanced
A 23-minute video from FOCS 2025: “A Little Clairvoyance Is All You Need”.
19:42Advanced
A 20-minute video from FOCS 2025: “A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams”.
24:39Advanced
A 25-minute video from FOCS 2025: “A distillation–teleportation protocol for fault-tolerant QRAM”.
19:41Advanced
A 20-minute video from FOCS 2025: “Adaptivity Gaps for Stochastic Probing with Subadditive Functions”.
25:56Advanced
A 26-minute video from FOCS 2025: “Adversarially robust quantum state learning and testing”.
21:14Advanced
A 21-minute video from FOCS 2025: “An Improved Greedy Approximation for (Metric) $k$-Means”.
18:53Advanced
A 19-minute video from FOCS 2025: “Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration”.
19:56Advanced
A 20-minute video from FOCS 2025: “Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest”.
17:42Advanced
A 18-minute video from FOCS 2025: “Computational-Statistical Tradeoffs from NP-hardness”.
27:40Advanced
A 28-minute video from FOCS 2025: “Computing the Polytope Diameter is Even Harder than NP-hard”.
16:52Advanced
A 17-minute video from FOCS 2025: “Deterministic factorization of constant-depth algebraic circuits in subexponential time”.
25:02Advanced
A 25-minute video from FOCS 2025: “Distributed Triangle Detection is Hard in Few Rounds”.
23:58Advanced
A 24-minute video from FOCS 2025: “Dynamic Treewidth in Logarithmic Time”.
17:23Advanced
A 17-minute video from FOCS 2025: “Edge-weighted Matching in the Dark”.
20:24Advanced
A 20-minute video from FOCS 2025: “Efficiently Batching Unambiguous Interactive Proofs”.
21:19Advanced
A 21-minute video from FOCS 2025: “Exponential improvements to the average-case hardness of BosonSampling”.
37:36Advanced
A 38-minute video from FOCS 2025: “Faster logconcave sampling from a cold start in high dimension”.
16:36Advanced
A 17-minute video from FOCS 2025: “Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics”.
20:47Advanced
A 21-minute video from FOCS 2025: “High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich”.
25:27Advanced
A 25-minute video from FOCS 2025: “How Global Calibration Strengthens Multiaccuracy”.
19:12Advanced
A 19-minute video from FOCS 2025: “Instance-Optimal Uniformity Testing and Tracking”.
20:57Advanced
A 21-minute video from FOCS 2025: “Lower Bounds for Non-adaptive Local Computation Algorithms”.
24:09Advanced
A 24-minute video from FOCS 2025: “Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade”.
17:02Advanced
A 17-minute video from FOCS 2025: “On the Impossibility of SNARGs with Short CRS”.
17:28Advanced
A 17-minute video from FOCS 2025: “Optimal 4-Approximation for the Correlated Pandora’s Problem”.
17:38Advanced
A 18-minute video from FOCS 2025: “Optimal Smoothed Analysis of the Simplex Method”.
24:56Advanced
A 25-minute video from FOCS 2025: “Overcomplete Tensor Decomposition via Koszul-Young Flattenings”.
18:45Advanced
A 19-minute video from FOCS 2025: “Quasipolynomial bounds for the corners theorem”.
16:48Advanced
A 17-minute video from FOCS 2025: “Robust Learning of Multi-index Models via Iterative Subspace Approximation”.
25:55Advanced
A 26-minute video from FOCS 2025: “Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching”.
21:25Advanced
A 21-minute video from FOCS 2025: “Shortest Paths on Convex Polyhedral Surfaces”.
17:31Advanced
A 18-minute video from FOCS 2025: “Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations”.
23:32Advanced
A 24-minute video from FOCS 2025: “The Power of Recursive Embeddings for $\ell_p$ Metrics”.
21:33
30:01Advanced
A 30-minute video from FOCS 2025: “Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time”.