Expander Graphs Overview || @ CMU || Lecture 16a of CS Theory Toolkit

Value of the Information & Strength of the Argument

The lecture provides a clear and comprehensive introduction to expander graphs, covering definitions, properties, and applications. The argumentation is solid, with mathematical definitions and proofs sketched for key results. The speaker emphasizes the importance of explicit constructions and motivates the need for them through applications. The lecture is well-structured, building from basic concepts to more advanced topics, and provides intuition alongside formal definitions.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is based on the survey ‘Expander graphs and their applications’ by Hoory, Linial, and Wigderson, which is a well-known and authoritative reference. The speaker is a professor at Carnegie Mellon University, adding credibility. The title accurately reflects the content. The lecture is rigorous, with precise definitions and references to prior work. The description includes links to the course homepage and the instructor’s page, but no direct link to the survey is provided.

The title accurately reflects the content: a comprehensive overview of expander graphs, including definitions, properties, applications, and constructions.

9/10

Lecture by a renowned professor at CMU, based on a well-known survey, with clear mathematical definitions and proofs sketches. The content is rigorous and well-structured, though it is a lecture and not peer-reviewed.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 00:00Introduction to expander graphs and their properties.
• 02:00Definition of sparse graphs and regular graphs.
• 04:00Discussion of conductance and edge expansion.
• 06:00Existence of expanders via probabilistic method.
• 08:00Definition of explicit and strongly explicit constructions.
• 10:00Introduction to bipartite expanders and their parameters.
• 12:00Applications in error-correcting codes and derandomization.
• 14:00Explicit constructions of bipartite expanders.

• Expander graphs and their applications — Mentioned as a resource for the lecture.
• Ryan O'Donnell's homepage — Instructor's page.
• Course homepage on Diderot — Course materials.
• Thumbnail photo by Rebecca Kiger — Photographer's page.

• Expander graphs and their applications — The survey mentioned in the lecture is a standard reference.