Results 281 - 290 of 24656
I will survey the remarkable progress on explicit constructions of randomness extractors for structured sources, including independent sources, small-space sources, and related models. Much of this progress has been driven by the development of powerful new primitives, such as non-malleable extractors, correlation breakers, and leakage-resilient extractors. I will discuss these notions, the connections between them, and discuss interesting open directions.
In this series of talks, we introduce coboundary expansion, a generalization of graph expansion to higher-dimensional complexes. Coboundary expansion can be understood both as a high-dimensional isoperimetric inequality and as a local testability property of codes arising from these complexes. We will first present the coding-theoretic definition of coboundary expansion. We will then introduce Gromov’s cone method, a fundamental technique for proving coboundary expansion. Finally, we will dive into an application of coboundary expansion: the Evra–Kaufman result that local spectral expanders with coboundary-expanding links give rise to locally testable codes.
Extremal eigenvalues of graphs are of particular interest in theoretical computer science and combinatorics. Specifically, the spectral gap—the difference between the largest and second-largest eigenvalues—measures the expansion properties of a graph.
In this talk, I will begin by providing background on the eigenvalues of random d-regular graphs and their connections to random matrix theory. Then I will discuss our results on eigenvalue rigidity and edge universality for these graphs. Eigenvalue rigidity asserts that, with high probability, each eigenvalue concentrates around its classical location as predicted by the Kesten-McKay distribution. Edge universality states that the second-largest eigenvalue and the smallest eigenvalue of random d-regular graphs converge to the Tracy-Widom distribution from the Gaussian Orthogonal Ensemble. Consequently, approximately 69% of d-regular graphs are Ramanujan graphs. Finally I will present a streamlined framework for proving the convergence to the random matrix statistics based on a microscopic version of the loop equations. These characterizations provide a direct route to universality: it suffices to verify the corresponding approximate loop equations for the ensemble under consideration. In many models, these equations follow from local laws and integration by parts.
Deep networks trained with finite step sizes exhibit non-monotonic, oscillatory loss. For full-batch gradient descent this is well charted: the quadratic model puts the stability boundary at twice the inverse step size, and deep neural networks rise to...
This mini course will give an introduction to hyperbolic surfaces. We will start with their basic topology and (hyperbolic) geometry. We will then introduce several random models for surfaces (some of which are directly defined using random graphs). In the end, we will give a taste of the ways in which many results about random surfaces parallel those for random graphs.
We present an introduction to the "L vs. BPL" problem, which asks whether randomness is ever necessary for space-efficient computation. We highlight four approaches to the problem: the "INW approach," the "Nisan approach," the "iterated restrictions approach," and the "inverse Laplacian approach."