Results 301 - 310 of 24656
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.
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.
The hardness versus randomness paradigm (initiated by Blum, Micali, Yao, Nisan and Wigderson) aims to show that randomized complexity classes can be derandomized assuming that certain complexity theoretic hardness assumptions hold. The key concept in this research is that of a pseudorandom generator, which stretches a short seed of random bits into a long string of pseudorandom bits that cannot be distinguished from uniform bits by any efficient algorithm. In the talk I will survey classical constructions of pseudorandom generators based on hardness assumptions, as well as implications of these constructions. I will also try to broadly survey some of the more recent work in this area.
Slides: https://www.cs.haifa.ac.il/~ronen/online_papers/simons_talk.pdf