Recent advances in vertex connectivity

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,900
Published on ● Video Link: https://www.youtube.com/watch?v=oXmc0OeoRzs


Duration: 14:24
227 views
5

Sorrachai Yingchareonthawornchai (Simons Institute)
https://simons.berkeley.edu/talks/sorrachai-yingchareonthawornchai-simons-institute-2023-09-08
Meet the Fellows Welcome Event Fall 2023

Vertex connectivity is a classic graph-theoretic notion that roughly measures the robustness of a graph against node failures. A classic open problem, asked by Aho, Hopcroft and Ullman in 1975, is whether or not vertex connectivity can be computed in linear time. In this short talk, I will give a quick survey on exciting developments on fast vertex connectivity algorithms in the past few years (since 2019) that culminate in a celebrated "poly-log max-flows" algorithm, leading to an almost linear time vertex connectivity algorithm by a recent breakthrough in max-flow algorithm.



Other Videos By Simons Institute for the Theory of Computing


2023-09-08What can the demand analyst learn from machine learning?
2023-09-08From Robustness to Privacy and Back
2023-09-08Decoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
2023-09-08Risk Convergence and Algorithmic Regularization of Discrete-Stepsize (Stochastic) Gradient Descent
2023-09-08Quantum Cryptography in Algorithmica
2023-09-08Noncommutative constraint satisfaction problems
2023-09-08Faster inverse maintenance for faster conic programming
2023-09-08Unifying strongly polynomial algorithms for subclasses of Linear Programs
2023-09-08Fast sparsification via convex optimization and chaining
2023-09-08Practical Graph Algorithms: Scalability and Privacy
2023-09-08Recent advances in vertex connectivity
2023-09-08Shortest paths, dynamic algorithms, and fine-grained complexity
2023-09-08Recent Trends in Minimum Cut Algorithms
2023-09-05Introduction to Data Structures and Optimization for Fast Algorithms
2023-09-01Optimization: Interior Point Methods Part 2
2023-09-01Optimization: Interior Point Methods Part 1
2023-09-01Matrix Data Structures
2023-08-31Optimization: Higher-order Methods Part 2
2023-08-31Sketching Part 4
2023-08-31Sketching Part 3
2023-08-31Sketching Part 2


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Meet the Fellows Welcome Event Fall 2023
Sorrachai Yingchareonthawornchai