Lecture
Unweighted Bipartite Matching
Related lectures (99)
Matroids: Matroid Intersection
Covers the concept of matroids, focusing on matroid intersection and the properties of subsets of a ground set.
Approximation Algorithms
Covers approximation algorithms for optimization problems, LP relaxation, and randomized rounding techniques.
Graph Sketching: Connected Components
Covers the concept of graph sketching with a focus on connected components.
Set Cover: Integrality Gap
Explores the integrality gap concept in set cover and multiplicative weights algorithms.
Cheeger's Inequalities
Explores Cheeger's inequalities for random walks on graphs and their implications.
Linear Programming: Weighted Bipartite Matching
Covers linear programming, weighted bipartite matching, and vertex cover problems in optimization.
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.
Information Theory: Basics
Covers the basics of information theory, entropy, and fixed points in graph colorings and the Ising model.
Linear Programming Duality
Covers linear programming duality and complementary slackness condition.
Graphical Models: Representing Probabilistic Distributions
Covers graphical models for probabilistic distributions using graphs, nodes, and edges.