Discrete Mathematics Courses and Certifications

Institute for Advanced Study

Localization Schemes - A Framework for Proving Mixing Bounds for Markov Chains

Explore a unified framework for proving mixing bounds in Markov chains, connecting Spectral Independence and Stochastic Localization techniques through the concept of localization schemes.

• YouTube
• 2 hours 5 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Locally Testable Codes with Constant Rate, Distance, and Locality, Part I - Irit Dinur

Explore locally testable codes with constant rate, distance, and locality. Learn about a new construction based on left-right Cayley complexes, addressing an open question in coding theory.

• YouTube
• 1 hour 6 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Pandora's Box with Correlations: Learning and Approximation - Shuchi Chawla

Explore decision-making under uncertainty, focusing on the Pandora's Box problem with correlated costs. Learn about adaptive strategies and data-driven algorithm design in this advanced computer science seminar.

• YouTube
• 1 hour 6 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Graph and Hypergraph Sparsification - Luca Trevisan

Explore graph and hypergraph sparsification techniques with Luca Trevisan, covering spectral definitions, irregular graphs, and unweighted graphs. Gain insights into advanced discrete mathematics concepts.

• YouTube
• 1 hour 34 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Geodesically Convex Optimization - Can We Prove P!=NP Using Gradient Descent - Avi Wigderson

Explore geodesically convex optimization and its potential to prove P≠NP using gradient descent in this advanced seminar by renowned mathematician Avi Wigderson.

• YouTube
• 1 hour 58 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Introduction to High Dimensional Expanders - Irit Dinur

Explore high dimensional expanders with Irit Dinur, covering random walks, spectral expansion, and hypergraphs. Gain insights into this advanced topic in discrete mathematics and computer science.

• YouTube
• 1 hour 51 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

An Introduction to Boolean Function Analysis - Dor Minzer

Explore Boolean function analysis, covering influences, PCP theory, and hypercontractive inequalities. Gain insights into fundamental concepts and advanced techniques in discrete mathematics and theoretical computer science.

• YouTube
• 1 hour 50 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen

Explore advanced topics in computational complexity, including circuit lower bounds, derandomization, and their connections. Gain insights into cutting-edge research and theoretical developments in computer science.

• YouTube
• 1 hour 7 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere

Explore advanced concepts in complexity theory, including proofs, circuits, and communication, with a focus on lower bounds and their implications for computational limits.

• YouTube
• 1 hour 59 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

MIP* = RE - Henry Yuen

Explore quantum correlations, nonlocal games, and entanglement models in this seminar on MIP* = RE, delving into complexity theory and efficient tests for quantum phenomena.

• YouTube
• 59 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Extremal Set Theory - Andrey Kupavskii

Explore extremal set theory with Andrey Kupavskii, covering shifting techniques, partial orders, and the Katniss Theorem. Gain insights into minimizing shadows and analyzing complex cases in discrete mathematics.

• YouTube
• 1 hour 52 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Sparse Matrices in Sparse Analysis - Anna Gilbert

Explore sparse matrices in compressive sensing, focusing on expander graphs and their applications. Learn about metric repair scenarios and algorithms for sparse signal recovery.

• YouTube
• 1 hour 2 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

A Brief Tour of Proof Complexity - Lower Bounds and Open Problems - Toniann Pitassi

Explore proof complexity, lower bounds, and open problems in computer science and discrete mathematics with insights on proof systems and their limitations.

• YouTube
• 1 hour 46 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

X-Ramanujan Graphs - Ex Uno Plures

Explore X-Ramanujan graphs with Ryan O'Donnell, covering additive lifts, generic graphs, eigenvalues, and matching polynomials in this advanced computer science and discrete mathematics seminar.

• YouTube
• 59 minutes
• Self-Paced
• Free Video

Institute for Advanced Study

Universality of Random Graphs - Gal Kronenberg

Explore 2-universality in random graphs, covering monotone properties, age universality, probability thresholds, and expansion properties with proof techniques and examples.

• YouTube
• 1 hour 9 minutes
• Self-Paced
• Free Video