{"id":300296,"date":"2016-10-02T22:00:36","date_gmt":"2016-10-03T05:00:36","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/?post_type=msr-event&p=300296"},"modified":"2022-08-08T09:58:31","modified_gmt":"2022-08-08T16:58:31","slug":"northwest-probability-seminar-2016","status":"publish","type":"msr-event","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/event\/northwest-probability-seminar-2016\/","title":{"rendered":"Northwest Probability Seminar 2016"},"content":{"rendered":"\n\n\n\n\n

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)<\/span><\/a> (PIMS).<\/p>\n\n\n\n

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

The day before the Northwest Probability Seminar, Steve Lalley (opens in new tab)<\/span><\/a> will speak at the UW-PIMS Mathematics Colloquium (opens in new tab)<\/span><\/a> on Return Probabilities of Random Walks on Non-Amenable Groups (opens in new tab)<\/span><\/a>. The talk will be at 2:30 pm in MEB 246 at University of Washington.<\/p>\n\n\n\n

There is no registration fee. Breakfast, lunch, and coffee will be free.<\/p>\n\n\n\n

The talks will take place in Building 99 at Microsoft. Parking at Microsoft is free.<\/p>\n\n\n\n

\"Participants<\/figure>\n\n\n\n

Schedule<\/h2>\n\n\n\n
10:00 \u2014 11:00<\/td>Coffee and muffins<\/td><\/tr>
11:00 \u2014 11:40<\/td>Lionel Levine (opens in new tab)<\/span><\/a> (Cornell University)
Random walks with local memory on Z and Z^2<\/em><\/a> [video<\/a>]<\/td><\/tr>
11:50 \u2014 12:30<\/td>Noah Forman (opens in new tab)<\/span><\/a> (University of Oxford \/ University of Washington)
Stationary diffusions on a space of interval partitions<\/em><\/a> [video (opens in new tab)<\/span><\/a>]<\/td><\/tr>
12:30 \u2014 1:40<\/td>Lunch (catered)<\/td><\/tr>
1:10 \u2014 2:15<\/td>Probability demos and open problems (overlaps with lunch)<\/td><\/tr>
2:20 \u2014 3:10<\/td>Alexei Borodin (opens in new tab)<\/span><\/a> (MIT; Birnbaum lecture)
Branching graphs and Integrable Probability<\/em><\/a> [video<\/a>]<\/td><\/tr>
3:20 \u2014 4:00<\/td>S\u00e9bastien Bubeck (opens in new tab)<\/span><\/a> (Microsoft Research)
Local max-cut in smoothed polynomial time<\/em><\/a> [video (opens in new tab)<\/span><\/a>]<\/td><\/tr>
4:00 \u2014 4:30<\/td>Tea and snacks<\/td><\/tr>
4:30 \u2014 5:10<\/td>Tom Hutchcroft (opens in new tab)<\/span><\/a> (University of British Columbia)
The strange geometry of high-dimensional spanning forests<\/em> [<\/a>video<\/a>]<\/td><\/tr>
6:00 \u2014<\/td>no host dinner at Oh India, Crossroads Mall, Bellevue<\/a><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

 <\/h2>\n\n\n\n

Titles and abstracts<\/h2>\n\n\n\n

Alexei Borodin (MIT)<\/h3>\n\n\n\n

Title: <\/em>Branching graphs and Integrable Probability<\/p>\n\n\n\n

Abstract: <\/em>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.<\/p>\n\n\n\n

S\u00e9bastien Bubeck (Microsoft Research)<\/h3>\n\n\n\n

Title: <\/em>Local max-cut in smoothed polynomial time<\/p>\n\n\n\n

Abstract: <\/em>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.<\/p>\n\n\n\n

Noah Forman (University of Oxford \/ University of Washington)<\/h3>\n\n\n\n

Title: <\/em>Stationary diffusions on a space of interval partitions<\/p>\n\n\n\n

Abstract: <\/em>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\u00e9vy 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.<\/p>\n\n\n\n

Tom Hutchcroft (University of British Columbia)<\/h3>\n\n\n\n

Title: <\/em>The strange geometry of high-dimensional spanning forests<\/p>\n\n\n\n

Abstract: <\/em>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.<\/p>\n\n\n\n

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<\/i> time the dimension increases, rather than just every four dimensions.<\/p>\n\n\n\n

Joint work with Yuval Peres.<\/p>\n\n\n\n

Lionel Levine (Cornell University)<\/h3>\n\n\n\n

Title: <\/em>Random walks with local memory on Z and Z^2<\/p>\n\n\n\n

Abstract: <\/em>The theme of this talk is walks in a random environment of \u201csignposts\u201d altered by the walker. I\u2019ll focus on three related examples:<\/p>\n\n\n\n

  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\u2019ll 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.<\/li>
  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\u2019ll 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.<\/li>
  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 \u201corganizes\u201d 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.<\/li><\/ol>\n\n\n\n

    Dinner info<\/h2>\n\n\n\n

    No host dinner (6:00 onwards) at Oh India, Crossroads Mall, 15600 NE 8th St, Bellevue, WA 98008 (opens in new tab)<\/span><\/a>.
    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.<\/p>\n\n\n\n\n\n

    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\u2019s airport, take I-405 north, then WA-520 east.<\/p>\n\n\n\n

    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 (opens in new tab)<\/span><\/a>.<\/p>\n\n\n\n\n\n

    Some nearby hotels include:<\/p>\n\n\n\n