Канал: Thatchaphol Saranurak - Смотреть видео c канала или скачать видео c канала в MP4, музыку MP3 на телефон или компьютер.

$Dynamic Spanning Forest with Worst-case Update Time: Adaptive, Las Vegas, and O(n^{1/2-eps})-time$

Basics of Length-Constrained Expanders and Low-step Flow Emulators

Thatchaphol Saranurak

Thatchaphol Saranurak

Basics of Length-Constrained Expanders and Low-step Flow Emulators

Robustness of Length-Constrained Expanders under Updates (Part 2)

Robustness of Length-Constrained Expanders under Updates (Part 1)

Expander Pruning

Lecture 13.2 Max flow via MWU and Boosting

Lecture 13.1 Using MWU to solve general linear programs and zero-sum games

Lecture 12.2 Choosing experts via Multiplicative Weights Update

Lecture 12.1 Small vertex connectivity in near-linear time via local algorithms

Lecture 11.2 Online LP rounding schemes for ski rental and online set covers

Lecture 11.1 Competitive analysis for online algorithms

Lecture 10.2 The primal-dual method for approximation algorithms

Lecture 10.1 Greedy and LP rounding methods for approximation algorithms

Lecture 9.2 Max-flow min-cut theorem via LP duality, Introduction to approximation algorithms

Lecture 9.1 Circulation, Maximum matching via blocking flow, linear programs, and LP duality

Lecture 8.2 Reductions to max flow

Lecture 8.1 Ford-Fulkerson and Dinic's algorithms, Maxflow-Mincut theorem

Lecture 7.2 Distributed graph sketching, Communication complexity

Lecture 7.1 Tug-of-War sketches and Johnson-Lindenstrauss lemma

Lecture 6.2 Sparse recovery (recap) l_0 sampling sketches

Lecture 6.1 Count-min sketches, Sparse recovery

Lecture 5.2 Perfect hashing, Cuckoo hashing

Lecture 5.1 Probability Primer, Hashing with chaining, Universal hashing families

Lecture 4.2 Splay trees, Dynamic edge orientations

Lecture 4.1 Amortized analysis methods, Fibonacci heaps

Lecture 3.2 Dijkstra, Even-Shiloach Tree for Dynamic Shortest Paths

Lecture 3.1 Traveling salesman, Bellman-Ford, Path-doubling, Floyd-Warshall, Intuition of Dijkstra

Lecture 2.2 More Dynamic Programming

Lecture 2.1 Basic Dynamic Programming

Lecture 1.2 Selection and maximum independent set

Lecture 1.1 Karatsuba and Fast Fourier Transform

Lecture 0 Invitation to TCS

Lecture 14 Summary

Dynamic Data Structures in Machine Learning by Omri Weinstein

The Lazy-Greedy Path to Efficient Amortised Dynamic Algorithms by Eva Rotenberg

Vertex sparsification in dynamic algorithms and beyond by Gramoz Goranci

Using expanders for dynamic graph algorithms: a survey of tools by Thatchaphol Saranurak

Recent advances in dynamic string algorithms by Tomasz Kociumaka

Dynamic algebraic algorithms for linear programs by Jan van den Brand

Dynamic matching algorithms and dynamic matching sparsifiers by David Wajc

Dynamic algorithms and optimization (Part 2) by Richard Peng

Dynamic algorithms and optimization (Part 1) by Richard Peng

Invitation to dynamic algorithms by Sayan Bhattacharya, Thatchaphol Saranurak

Lecture 1.1 (8 31 2021) Introduction, Definitions of expanders

Lecture 1.2 (9 2 2021) Robustness of expanders, Sublinear-time connectivity after failures

Lecture 1.3 (9 3 2021) Discussion

Lecture 2.1 (9 7 2021) Leighton-Rao's metric relaxation

Lecture 2.2 (9 9 2021) Bourgain's metric embedding

Lecture 2.3 (9 10 2021) Discussion

Lecture 3.1 (9 14 2021) Approximate max-flow min-cut theorem

Lecture 3.2 (9 16 2021) Cut/flow equivalences among expanders

Lecture 3.3 (9 17 2021) Discussion

Lecture 4.1 (9 21 2021) Cheeger's Inequality

Lecture 4.2 (9 23 2021) The power method

Lecture 4.3 (9 24 2021) Discussion

Lecture 14.3 (12 10 2021) Summary

Lecture 13.1 (11 30 2021) Boundary-linked decomposition, Vertex Cut Sparsifier

Lecture 5.3 (10 1 2021) Discussion

Lecture 14.2 (12 9 2021) Approximate max-flow in almost linear time (continued), Summary

Lecture 12.5 (11 19 2021) Discussion (second half, no slides)

Lecture 10.3 (11 5 2021) Discussion

Lecture 6.3 (10 8 2021) Discussion

Lecture 10.1 (11 2 2021) Spanners and cut sparsifiers from expander decomposition

Lecture 10.2 (11 4 2021) Deterministic Mincut via Exact Non-trivial mincut sparsifier

Lecture 9.2 (10 28 2021) Expander decomposition: existence and construction

Lecture 9.3 (10 29 2021) Discussion

Lecture 7.1 (10 12 2021) Applications of isolating cuts and local min cuts, Intro cut-matching game

Lecture 6.2 (10 7 2021) Isolating cuts, local cuts

Lecture 12.3 (11 18 2021) Dynamic/Local flow, Expander Pruning

Lecture 7.2 (10 14 2021) Deterministic slow algorithms for the cut player (KKOV)

Lecture 5.1 (9 28 2021) Spectral equivalence of expanders, Expander mixing lemma, Ramanujan graphs

Lecture 8.2 (10 22 2021) Discussion

Lecture 11.1 (11 11 2021) Introduction to the push-relabel framework

Lecture 6.1 (10 5 2021) Mixing time, Connectivity in log space Short paths in sqrt{n} time

Lecture 12.4 (11 19 2021) Discussion (first half, audio only)

Lecture 8.1 (10 21 2021) Randomized fast algorithms for the cut player (KRV)

Lecture 12.2 (11 16 2021) Push relabel via dynamic trees

Lecture 12.1 (11 16 2021) Max flow in ~O(mn) and Balanced Sparse cut in nearlinear time