Lectures related to Cheeger's Inequalities

Explores the convergence of random walks on graphs and the properties of weighted adjacency matrices.

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.

Graph Sketching: Connected Components

Covers the concept of graph sketching with a focus on connected components.

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.

Matroids: Matroid Intersection

Covers the concept of matroids, focusing on matroid intersection and the properties of subsets of a ground set.

Cheeger's Inequality

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

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Unweighted Bipartite Matching

Introduces unweighted bipartite matching and its solution using linear programming and the simplex method.

Polynomial Identity Testing

Covers polynomial identity testing using oracles and random point evaluation, with applications in graph theory and algorithmic aspects.

Approximation Algorithms

Covers approximation algorithms for optimization problems, LP relaxation, and randomized rounding techniques.

Networked Control Systems: Opportunities

Explores coordination in networked control systems, graph theory, and consensus algorithms.

Interlacing Families and Ramanujan Graphs

Explores interlacing families, Ramanujan graphs, and their construction using signed adjacency matrices.

Graph Algorithms: Ford-Fulkerson and Strongly Connected Components

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

Belief Propagation

Explores Belief Propagation in graphical models, factor graphs, spin glass examples, Boltzmann distributions, and graph coloring properties.

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Graph Algorithms: Modeling and Traversal

Covers graph algorithms, modeling relationships between objects, and traversal techniques like BFS and DFS.

Algorithms: Union Find and Minimum Spanning Trees

Discusses Union-Find data structures and Minimum Spanning Trees, covering algorithms and their applications in network design and optimization.

Graphical Models: Probability Distributions and Factor Graphs

Covers graphical models for probability distributions and factor graphs representation.

Interlacing Families and Ramanujan Graphs

Explores interlacing families of polynomials and 1-sided Ramanujan graphs, focusing on their properties and construction methods.

Spectral Graph Theory: Introduction

Introduces Spectral Graph Theory, exploring eigenvalues and eigenvectors' role in graph properties.