Nodal Domains of G(n,p) Graphs

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=ItMCuWiDRcI


Duration: 54:42
219 views
2

Mark Rudelson (University of Michigan)
Probability, Geometry, and Computation in High Dimensions
Seminar, Sep. 15, 2020
https://simons.berkeley.edu/events/nodal-domains-gnp-graphs

A nodal domain of a graph is a connected component of an eigenvector of its Laplacian. Nodal domains of compact manifolds are classical objects in geometry, and their number typically increases as the eigenvalue increases. About 12 years ago, Dekel, Lee, and Linial showed that in contrast to the manifolds, the number of nodal domains of a G(n,p) graph remains constant with high probability. In this talk, we will discuss how the properties of nodal domains are related to delocalization of eigenvectors, and show that the positive and the negative nodal domains of a G(n.p) graph have almost the same size with high probability.

Joint work with Han Huang.



Other Videos By Simons Institute for the Theory of Computing


2020-09-25Pedagogical Talk: Frameworks for Information-Computation Tradeoffs
2020-09-25Reducibility and Statistical-Computational Gaps from Secret Leakage
2020-09-25Berkeley in the 80s, Episode 4: Andrew Yao
2020-09-25Free Energy Wells and Overlap Gap Property in Sparse PCA
2020-09-25The Overlap Gap Property in Principal Submatrix Recovery
2020-09-24Phase Retrieval in High Dimensions: Statistical and Computational Phase Transitions
2020-09-24Pedagogical Talk: Failure of Low-Degree Polynomials
2020-09-24The Rank of Sparse Random Matrices
2020-09-24Sampling From the Random Cluster Model at All Temperatures on Random Graphs
2020-09-24Correlation Decay for Hard Spheres via Markov Chains
2020-09-23Nodal Domains of G(n,p) Graphs
2020-09-23Pedagogical Talk: Random Optimisation Problems
2020-09-23Information/Computation Gaps in Heavy-Tailed Statistics
2020-09-23The Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
2020-09-23Thresholds of Descending Algorithms in Inference Problems
2020-09-23Optimization of Full-RSB Spherical Spin Glasses
2020-09-22A Positivity-First Approach to Sum-of-Squares Over the Hypercube
2020-09-22Equitable Colorings
2020-09-21Counting Solutions to Random CNF Formulas
2020-09-21Incremental Approximate Message Passing
2020-09-21Local Statistics, Semidefinite Programming, and Community Detection II


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing