## Summary

The 18th Northwest Probability Seminar, a one-day mini-conference organized by the University of Washington, the Oregon State University, the University of British Columbia, the University of Oregon, and the Theory Group at Microsoft Research, will be held on November 5, 2016. This year the conference is hosted at Microsoft, supported by Microsoft Research and the Pacific Institute for the Mathematical Sciences (PIMS).

The Birnbaum Lecture in Probability will be given by Alexei Borodin (MIT). [Past Birnbaum speakers] Other speakers are Sébastien Bubeck (Microsoft Research), Noah Forman (University of Oxford / University of Washington), Tom Hutchcroft (University of British Columbia), and Lionel Levine (Cornell University).

The day before the Northwest Probability Seminar, Steve Lalley will speak at the UW-PIMS Mathematics Colloquium on Return Probabilities of Random Walks on Non-Amenable Groups. The talk will be at 2:30 pm in MEB 246 at University of Washington.

There is no registration fee. Breakfast, lunch, and coffee will be free.

The talks will take place in Building 99 at Microsoft. Parking at Microsoft is free.

## Schedule

10:00 — 11:00 | Coffee and muffins |

11:00 — 11:40 | Lionel Levine (Cornell University)Random walks with local memory on Z and Z^2 [video] |

11:50 — 12:30 | Noah Forman (University of Oxford / University of Washington)Stationary diffusions on a space of interval partitions [video] |

12:30 — 1:40 | Lunch (catered) |

1:10 — 2:15 | Probability demos and open problems (overlaps with lunch) |

2:20 — 3:10 | Alexei Borodin (MIT; Birnbaum lecture)Branching graphs and Integrable Probability [video] |

3:20 — 4:00 | Sébastien Bubeck (Microsoft Research)Local max-cut in smoothed polynomial time [video] |

4:00 — 4:30 | Tea and snacks |

4:30 — 5:10 | Tom Hutchcroft (University of British Columbia)The strange geometry of high-dimensional spanning forests [video] |

6:00 — | no host dinner at Oh India, Crossroads Mall, Bellevue |

## Titles and abstracts

### Alexei Borodin (MIT)

*Title: *Branching graphs and Integrable Probability

*Abstract: *The goal of the talk is to survey the emerging field of integrable probability, whose goal is to identify and analyse exactly solvable probabilistic models. The models and results are often easy to describe, yet difficult to find, and they carry essential information about broad universality classes of stochastic processes.

### Sébastien Bubeck (Microsoft Research)

*Title: *Local max-cut in smoothed polynomial time

*Abstract: *The local max-cut problem asks to find a partition of the vertices in a weighted graph such that the cut weight cannot be improved by moving a single vertex (that is the partition is locally optimal). This comes up naturally, for example, in computing Nash equilibrium for the party affiliation game. It is well-known that the natural local search algorithm for this problem might take exponential time to reach a locally optimal solution. We show that adding a little bit of noise to the weights tames this exponential into a polynomial. In particular we show that local max-cut is in smoothed polynomial time (this improves the recent quasi-polynomial result of Etscheid and Roglin).

Joint work with Omer Angel, Yuval Peres, and Fan Wei.

### Noah Forman (University of Oxford / University of Washington)

*Title: *Stationary diffusions on a space of interval partitions

*Abstract: *We construct two diffusions on a space of partitions of the unit interval. These are stationary with the law of the complement of the zero sets of Brownian motion and Brownian bridge, respectively. Our construction is based on decorating the jumps of a spectrally positive Lévy process with independent continuous excursions. The processes of ranked interval lengths of our partitions belong to a two parameter family of diffusions introduced by Ethier and Kurtz (1981) and Petrov (2009). These are continuum limits of up-down Markov chains on Chinese restaurant processes. Our construction works towards building a diffusion on the space of real trees whose existence has been conjectured by Aldous.

### Tom Hutchcroft (University of British Columbia)

*Title: *The strange geometry of high-dimensional spanning forests

*Abstract: *The uniform spanning forest (USF) of Z^d, first studied by Pemantle (1991), is defined as an infinite-volume limit of uniform spanning trees of large finite boxes. Although it is defined as a limit of trees, the USF is not necessarily connected. Indeed, Pemantle proved the surprising theorem that the USF of Z^d is connected if and only if d =< 4. Later, Benjamini, Kesten, Peres, and Schramm (2004) extended this result, discovering a remarkable phenomenon in the way the geometry of the USF changes as the dimension increases: For dimensions 5 =< d =< 8, there are infinitely many trees, but every tree touches every other tree. For 9 =< d =< 12, there are trees that do not touch, but for every two trees we can find an intermediary tree that touches each of the two trees. They proved that this pattern continues, with the number of intermediary trees required increasing by one every time the dimension increases by four.

In this talk, I will show that this result is not the whole story, and that in fact the USF undergoes qualitative changes to its geometry *every* time the dimension increases, rather than just every four dimensions.

Joint work with Yuval Peres.

### Lionel Levine (Cornell University)

*Title: *Random walks with local memory on Z and Z^2

*Abstract: *The theme of this talk is walks in a random environment of “signposts” altered by the walker. I’ll focus on three related examples:

1. Rotor walk on Z^2. Your initial signposts are independent with the uniform distribution on {North,East,South,West}. At each step you rotate the signpost at your current location clockwise 90 degrees and then follow it to a nearest neighbor. Priezzhev et al. conjectured that in n such steps you will visit order n^{2/3} distinct sites. I’ll outline an elementary proof of a lower bound of this order. The upper bound, which is still open, is related to a famous question about the path of a light ray in a grid of randomly oriented mirrors. This part is joint work with Laura Florescu and Yuval Peres.

2. p-rotor walk on Z. In this walk you flip the signpost at your current location with probability 1-p and then follow it. I’ll explain why your scaling limit will be a Brownian motion perturbed at its extrema. This part is joint work with Wilfried Huss and Ecaterina Sava-Huss.

3. p-rotor walk on Z^2. Rotate the signpost at your current location clockwise with probability p and counterclockwise with probability 1-p, and then follow it. This walk “organizes” its initially disordered environment of signposts. The stationary environment is an orientation of the uniform spanning forest, plus one additional edge. This part is joint work with Swee Hong Chan, Lila Greco and Boyao Li.

## Dinner info

No host dinner (6:00 onwards) at Oh India, Crossroads Mall, 15600 NE 8th St, Bellevue, WA 98008.

The entrance to the restaurant is on the outside of the main mall building, on the North side, behind Barnes and Noble and opposite Sports Authority. The food is Indian buffet, with many vegetarian and non-vegetarian options available. Price $15 per person.

## Directions

From the north: Take I-5 south, then I-405 south, then WA-520 east.

From the south: Take I-5 north, then I-405 north, then WA-520 east.

From Seattle: Take WA-520 east.

By airplane: Fly to Seattle’s airport, take I-405 north, then WA-520 east.

From WA-520 east, take the 148th Ave NE North exit (this is the second 148th Ave NE exit). Turn right (north) onto 148th Ave NE, proceed a few blocks, and turn right onto NE 36th St. Building 99 will be on the left. The address is 14820 NE 36th St, Redmond, WA 98052-5319. Click here for a map with directions.

## Hotels

Some nearby hotels include

- Extended Stay America (probably the best choice)

15805 NE 28th Street

Bellevue, WA 98008

(425) 885-6675 - Silver Cloud Inn

10621 NE 12th Street

Bellevue, WA 98004

(800) 205-6937 - Courtyard Marriott (extremely close)

14615 NE 29th Place

Bellevue, WA 98007

(425) 869-5300 - Fairfield Inn Marriott (extremely close)

14595 NE 29th Place

Bellevue, WA 98007

(425) 869-6548 - Residence Inn Marriott-Redmond

7575 164th Ave NE

Redmond, WA 98052

(425) 497-9226 - Silver Cloud Inn (near the University of Washington in Seattle)

5036 25th Avenue NE

Seattle, WA 98105

(800) 205-6940 - University Inn (near the University of Washington)

4140 Roosevelt Way NE

Seattle, WA 98105

(800) 733-3855 - Watertown (near the University of Washington)

4242 Roosevelt Way NE

Seattle, WA 98105

(866) 944-4242