Russell Lyons writes this profile of IMS Fellow Yuval Peres, who was elected as a foreign associate of the US National Academy of Sciences in May 2016.

Yuval Peres

Yuval Peres, Principal Researcher in the Theory Group at Microsoft Research in Redmond, WA, was elected as a foreign associate of the US National Academy of Sciences in 2016. The requirements to be a foreign associate are even higher than those for US citizens to be elected.

Born in 1963 in Israel, Peres obtained his PhD at the Hebrew University of Jerusalem in 1990, directed by Hillel Furstenberg. After postdoctoral positions at Stanford and Yale Universities, he advanced through the ranks as faculty at both the Hebrew University and the University of California at Berkeley.

Peres joined Microsoft Research in 2006, where he leads the Theory Group. This group combines mathematicians and computer scientists working on probability and algorithms. It attracts many visitors from around the world for both long and short stays.

The broad categories of Peres’ research are probability, ergodic theory and fractals, Markov chains and random walks, game theory, and Brownian motion. More particularly, he specializes in stochastic processes on graphs, such as random walks, percolation, and other topics from statistical physics; Bernoulli convolutions; the p-Laplacian; mixing times; combinatorics, especially random graphs; geometric group theory; martingales; and point processes. In computer science, he has posted papers to the arXiv in five different primary sections: game theory, information theory, learning, data structures and algorithms, and computational complexity. Peres is prolific and gregarious: He has close to 300 papers and 200 coauthors; he has more than ten joint works with each of multiple long-term collaborators; and he has co-authored three books on probability that have been quite popular and is working on other books in game theory and analysis. Several of his 21 PhD students have become very successful mathematicians in their own right.

Peres has accumulated several honors: the Rollo Davidson Prize in 1995 and the Loève Prize in 2001; invitations to speak at the International Congress of Mathematicians in 2002 and the European Congress of Mathematics in 2008; the David P. Robbins Prize (shared) in 2011; and fellowship of the IMS in 2008 and the American Mathematical Society in 2012. He has given distinguished lectures at UCLA, Tel Aviv University, the Rényi Institute, the University of British Columbia, Carnegie Mellon University (in Computer Science), Rice University, Indiana University, the University of North Carolina, and the University of Colorado. Peres has served on scientific boards of several organizations, including PIMS, AIM, and IPAM.

With his great technical acuity and encyclopedic knowledge, Peres has established a large number of fundamental and deep results. Many of these find new connections between different areas in probability, and sometimes analysis. For example, with Kenyon, he discovered how intersections of fractals are connected to growth of random matrix products; he related percolation on trees to intersections of Brownian motion; with Levine, he analyzed the rotor-router model via free boundary problems; with Ding and Lee, he related cover times for random walks to Talagrand’s theory of maxima of Gaussian processes; with Sheffield, Schramm, and Wilson, he analyzed the p-Laplacian via random-turn games; with Solomyak and later Schlag, he connected Bernoulli convolutions to generalized random projections; with Austin and Naor, he bounded the compression of groups via random walks; and with Virág, he found that the zeros of a certain Gaussian analytic function form a determinantal point process.

There is space here to describe only a few of Peres’ accomplishments in any detail. We focus on random walks. Random walks are fundamental in all of science, including computer science. Some of the deepest results known about them are due to Peres and his coauthors.

In a paper with Dembo, Rosen, and Zeitouni that appeared in Acta Math., he considered simple random walk on ℤ². This Markov chain is recurrent, so each point will be visited infinitely often a.s. How fast does the number of visits increase? Consider the most-often visited point after n steps. Solving a 40-year-old conjecture of Erdós and Taylor, Peres et al. proved that it is a.s. asymptotic to (log n)²/π. The proof is a tour-de-force, using a novel multiscale refinement of the classical second-moment method in order to handle high correlations of the local times at different sites.

Another paper with the same authors that appeared in Ann. Math. again concerned simple random walk on ℤ². In the old days when screensavers actually had a practical purpose, one such program simply performed a random walk on the pixels of the screen, turning each one off when visited. A mathematician viewing such a display will be curious how long, on average, it will take until the entire screen is off. This is an example of the cover time of a random walk on a finite graph. In fact, this graph parameter has been studied intensively since about 1980 by probabilists, combinatorialists, and computer scientists. It has applications to designing universal traversal sequences, testing graph connectivity, and protocol testing, among others. Peres et al. established a 15-year-old conjecture due to Aldous that the number of steps it takes to cover all points of the lattice torus ℤ²_n is asymptotic to 4n²(log n)²/π. While the exact (asymptotic) value is elegant and satisfying, there is actually much more importance in simply knowing that such a limit exists, regardless of the actual constant (4/π in this case). This is because as the random walk visits more and more nodes of the graph, the uncovered nodes form a fractal-type random object; this object itself had been studied by physicists via simulations and (non-rigorous) heuristic arguments. In order to make such study rigorous, the first step is to establish that such precise asymptotics for the cover time exist.

A paper with Ding and Lee that also appeared in Ann. Math. continued Peres’ deep study of the cover time of graphs, but now for general finite graphs. He found a strong and surprising connection to Gaussian processes. This allowed him to resolve a number of open questions: Aldous and Fill asked in 1994 whether one can efficiently compute the cover time up to a bounded factor (where the bound does not depend on the graph). Peres et al. provided such an algorithm. A notion of cover time that takes longer is known as the blanket time; in 1996, Winkler and Zuckerman conjectured that the blanket time is actually no larger than a constant times the cover time; Peres et al. proved that this is true. Prior to this work, instead of a constant independent of all graphs, the best previous approximation factor (for both these problems) was O(log log n)² for n-vertex graphs; this was due to Kahn, Kim, Lovász, and Vu.

Peres is widely known for his sense of humor. His favorite quote is from his son Alon, who was overheard at age 6 asking a friend: “Leo, do you have a religion? You know, a religion, like Christian, or Jewish, or Mathematics …?”