Results 81 - 90 of 24633
Sparse random graphs provide a natural setting in which to study ideas from quantum chaos. Despite the strong dependencies among their matrix entries, many spectral features of these graphs resemble those of classical random matrix ensembles. This can be viewed as an example of the broader phenomenon of universality: many spectral properties are shared across random matrix ensembles and depend on only a small amount of information about the underlying model. In this talk, we will discuss some recent results in this direction and explain some of the main ideas behind this progress. Central to the analysis are combinatorial analogues of tools from random matrix theory, together with local modifications of the graph that recover enough approximate independence to study universal spectral behavior.
In this talk, I will discuss spectral methods for studying hypergraphs. I will introduce the Kikuchi graph, a construction that turns a k-uniform hypergraph into an ordinary graph. Studying the spectral properties of such graphs has led to several surprising applications. I will focus on two of them: the hypergraph Moore bound, and lower bounds for locally decodable codes.
We present here the first part of Jorge Garza-Vargas’s three-part mini-course on the strong convergence phenomenon, from our ICM Satellite Conference on Spectral Theory, High-Dimensional Expansion, and Pseudorandomness. The course introduces and motivates the notion of strong convergence, discusses recent proof techniques, and showcases concrete applications.
High-dimensional expansion (HDX) is a generalization of expansion in graphs to higher dimensions (i.e., hypergraphs). In this first of three lectures from our ICM satellite conference, Mitali Bafna defines the spectral notion of HDX, proves the trickle-down theorem, and defines random walks on HDX.
In this presentation from this fall’s joint boot camp for the programs on Spectral Theory Beyond Graphs and on Pseudorandomness & High-Dimensional Expansion, William Hoza presents an introduction to the “L vs. BPL” problem, which asks whether randomness is ever necessary for space-efficient computation.
Eugenia Sapir’s mini-course provides an introduction to hyperbolic surfaces, including their basic topology and (hyperbolic) geometry, several random models for surfaces (some of which are directly defined using random graphs), and the ways in which many results about random surfaces parallel those for random graphs.
Register for the lecture here.
Expander graphs are sparse graphs for which, whenever you split the graph into two parts, the number of edges going between the parts is proportional to the size of the smaller part. There are extremely simple, strongly explicit expander families whose analysis requires only a tiny bit of group theory. This fact is perhaps not so widely known. In this lecture, Ryan O’Donnell will show some of these constructions/analyses, and also indicate how they can be used to get even stronger kinds of expanders, such as “super-expanders,” and “non-sofic property (T) groups.”
Ryan O’Donnell is a Professor of Computer Science at Carnegie Mellon University. He received his BSc from the University of Toronto in 1999, and his PhD in applied mathematics from MIT in 2003, where he was advised by Madhu Sudan. His research interests include complexity theory, quantum computation, and spectral graph theory. He is the author of the book Analysis of Boolean Functions.
Refreshments will be served at 3 p.m., before the event.
The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science and is geared toward a broad scientific audience.
The lecture recording URL will be emailed to registered participants. This URL can be used for access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about five days following each presentation unless otherwise noted.
The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials.
If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.
No abstract available.
No abstract available.