Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Pseudorandomness: Theory and Applications

In course

MATH-467: Probabilistic methods in combinatorics

The 'probabilistic method' is a fundamental tool in combinatorics. The basic idea is as follows: to prove that an object (for example, graph) with certain properties exists, it suffices to prove that if the object is chosen at random, then it has the desir ...

Description

This lecture covers the concept of pseudorandomness, focusing on the theory and applications. It discusses the importance of pseudorandomness in AI, the challenges of testing properties with exponentially small probabilities, and the idea of pseudo-random graphs. The lecture also delves into the theory of dynamical systems, looking at manifolds and random walks on surfaces. It explores the transition matrix in random walks, Laplacian matrices, and the properties of adjacency matrices. Additionally, it explains the relationship between eigenvalues and eigenvectors in adjacency and Laplacian matrices, emphasizing the significance of pseudorandomness in various applications.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Algebra: Linear algebra

Related concepts (32)

Laplacian matrix

In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method. The Laplacian matrix relates to many useful properties of a graph.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

List of graphs

This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.

Color

Color (American English) or colour (Commonwealth English) is the visual perception based on the electromagnetic spectrum. Though color is not an inherent property of matter, color perception is related to an object's light absorption, reflection, emission spectra and interference. For most humans, color are perceived in the visible light spectrum with three types of cone cells (trichromacy). Other animals may have a different number of cone cell types or have eyes sensitive to different wavelength, such as bees that can distinguish ultraviolet, and thus have a different color sensitivity range.

Related lectures (46)

Graphical Models: Representing Probabilistic Distributions

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

Graphs: Properties and Representations

Covers graph properties, representations, and traversal algorithms using BFS and DFS.

Automorphism Groups: Trees and Graphs III

Explores automorphism groups of trees and graphs, including actions on trees and group homomorphisms.

Linear Algebra: Diagonalization

Explores the diagonalization of matrices and the conditions for exact diagonalization, with examples demonstrating the process.

Graphs and matrices