Concept

Cut (graph theory)

Related lectures (28)

Explores Bourgain's theorem on sparsest cut in graphs, emphasizing semimetrics and cut optimization.

Ford-Fulkerson Method: Max Flow and Min Cut

Explores the Ford-Fulkerson method for finding max flow and min cut in a network.

Explores the equivalence between maximum flow and minimum cut in network theory, demonstrating its applications through examples and edge-disjoint paths.

Ford-Fulkerson Method

Introduces the Ford-Fulkerson Method to find the maximum flow in a network.

Low Diameter Random Partitioning

Discusses Low Diameter Randomized Decomposition and graph partitioning for edge cuts and coloring.

Graph Algorithms: Ford-Fulkerson and Strongly Connected Components

Discusses the Ford-Fulkerson method and strongly connected components in graph algorithms.

Stein Algorithm: Polynomial Identity Testing

Explores the Stein algorithm for polynomial identity testing and the minimization of a cut problem.

Cheeger's Inequality

Explores Cheeger's inequality and its implications in graph theory.

Shape From Stereo-2

Explores stereo vision concepts such as occlusions, window size impact, multi-view stereo, dynamic shape reconstruction, and graph-based segmentation.

Segmentation: Theory and Algorithms

Covers the theory and algorithms behind image segmentation, focusing on region identification and evaluation.

Semi-Definite Programming

Covers semi-definite programming and optimization over positive semidefinite cones.

Graph Sketching: Connected Components

Covers graph sketching and connected components in streaming models.

Max-Flow Problem: Ford-Fulkerson Algorithm

Explores the Ford-Fulkerson algorithm for solving the Max-Flow problem and its applications in network flow optimization.

Sparsest Cut and Concurrent Flow

Covers sparsest cut, NP-completeness, Bougains Theorem, and concurrent flow in graphs.

Sparsest Cut: ARV Theorem

Covers the proof of the Bourgain's ARV Theorem, focusing on the finite set of points in a semi-metric space and the application of the ARV algorithm to find the sparsest cut in a graph.

Submodular Function Minimization

Covers submodular functions and their minimization, emphasizing diminishing returns and the Lovász Extension.

Clustering: K-means & LDA

Covers clustering using K-means and LDA, PCA, K-means properties, Fisher LDA, and spectral clustering.

Max-Cut Problem: SDP Relaxation and Randomized Rounding

Explores the Max-Cut Problem, its relaxation using SDP, and Polynomial Optimization.

Sparsest Cut: Leighton-Rao Algorithm

Covers the Leighton-Rao algorithm for finding the sparsest cut in a graph, focusing on its steps and theoretical foundations.

Quantum Approximate Optimization Algorithm

Covers the Quantum Approximate Optimization Algorithm, physically inspired unitary coupled cluster ansatz, hardware-efficient ansatz, and variational quantum eigensolver.