Nov 17, 2016

Profile: Yuval Peres

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

 

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 2. 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)2/π. 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 2. 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 2n 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 …?”

Share

1 Comment

  • I am inspired by Yuval Peres. He is very humble.

Leave a comment

*

Share

Welcome!

Welcome to the IMS Bulletin website! We are developing the way we communicate news and information more effectively with members. The print Bulletin is still with us (free with IMS membership), and still available as a PDF to download, but in addition, we are placing some of the news, columns and articles on this blog site, which will allow you the opportunity to interact more. We are always keen to hear from IMS members, and encourage you to write articles and reports that other IMS members would find interesting. Contact the IMS Bulletin at bulletin@imstat.org

What is “Open Forum”?

In the Open Forum, any IMS member can propose a topic for discussion. Email your subject and an opening paragraph (to bulletin@imstat.org) and we'll post it to start off the discussion. Other readers can join in the debate by commenting on the post. Search other Open Forum posts by using the Open Forum category link below. Start a discussion today!

About IMS

The Institute of Mathematical Statistics is an international scholarly society devoted to the development and dissemination of the theory and applications of statistics and probability. We have about 4,500 members around the world. Visit IMS at http://imstat.org
Latest Issue