AF SMALL : New Frontiers in Expansion

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

In a network, such as a road network or a social network, there is tension between the number of links it has and how “well-connected” it is --- in particular, it seems having very few links should make it hard to get from one place to another. However, there is a special type of network called an expander graph in which this intuition is misleading: there are very few (say, 3) links per node, but nonetheless, when taking a random walk on such a graph, the walker gets completely lost in very few steps, a process known as mixing. This surprising phenomenon has been very useful in computer science and is an essential ingredient in many fields, including error-correcting codes, cryptography, fault-tolerant computation, statistical mechanics, and more. This project addresses two kinds of mysteries that remain regarding expansion. First, we still don’t know the optimal tradeoff between the sparsity of a network and its rate of mixing, articulated in various ways. This tradeoff is important because it directly affects the performance of algorithms based on expanders. Second, our understanding of quantum generalizations of expansion is still in its infancy --- roughly speaking, these are notions of mixing that would be useful in simulating quantum statistical mechanical systems rather than classical ones, and we don’t understand mathematically when such mixing happens. This project will attempt to answer these questions, which will potentially lead to faster algorithms in coding theory and quantum computation. At a technical level, the project will pursue the following questions: (A) The existence of optimally expanding (nonbipartite) “Ramanujan” graphs--- which are expander graphs with second eigenvalue as small as possible --- employing insights from the geometry of polynomials and free probability theory. (B) The construction of a certain kind of optimal error-correcting code called an “epsilon-biased code” via a finer study of random walks on Ramanujan and related graphs, employing insights from mathematical physics on graphs. (C) Proofs of rapid mixing for “Quantum Markov Chains" converging to thermal states of quantum systems, generalizing what is known in the classical case. This work offers an opportunity to discover new mathematical connections between theoretical computer science and the aforementioned areas of mathematics. The investigator will organize an interdisciplinary program to cultivate these connections and bring together the people working in these areas. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.