November 5, 2016

Northwest Probability Seminar 2016

Location: Microsoft Research 99/1919

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 (opens in new tab) (PIMS).

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

The day before the Northwest Probability Seminar, Steve Lalley (opens in new tab) will speak at the UW-PIMS Mathematics Colloquium (opens in new tab) on Return Probabilities of Random Walks on Non-Amenable Groups (opens in new tab). 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.

Participants of the Northwest Probability Seminar 2016

Schedule

10:00 — 11:00Coffee and muffins
11:00 — 11:40Lionel Levine (Cornell University)
Random walks with local memory on Z and Z^2 [video]
11:50 — 12:30Noah Forman (University of Oxford / University of Washington)
Stationary diffusions on a space of interval partitions [video]
12:30 — 1:40Lunch (catered)
1:10 — 2:15Probability demos and open problems (overlaps with lunch)
2:20 — 3:10Alexei Borodin (MIT; Birnbaum lecture)
Branching graphs and Integrable Probability [video]
3:20 — 4:00Sébastien Bubeck (Microsoft Research)
Local max-cut in smoothed polynomial time [video]
4:00 — 4:30Tea and snacks
4:30 — 5:10Tom 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 (opens in new tab).
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.