The 3rd Pacific Northwest Theory Day

  • Start Date: 05/04/2013
  • End Date: 05/05/2013


Confirmed Speakers:

 Paul Beame (U Washington)
 Josh Benaloh (Microsoft Research)

 George Giakkoupis (INRIA Rennes)

 Nick Harvey (UBC)

 Valerie King (UVic)

 Konstantin Makarychev (Microsoft Research)

 Anup Rao (U Washington)
 Cenk Sahinalp (SFU)
 Roger Wattenhofer (ETH Zurich and Microsoft Research)

 Philipp Woelfel (UCalgary)
 David Woodruff(IBM Almaden)


University of Victoria

This is a chance to bring together researchers and students from the region, including Microsoft Research, Simon Fraser University, University of British Columbia, University of Calgary, University of Washington, and University of Victoria.

This year is especially exciting, as with the funding provided by the PIMS Collaborative Research Group on Algorithmic Theory of Networks we are inviting outside speakers, extending the event to two days and aiming for a special focus on Algorithmic Theory of Networks and Randomized Techniques.

In keeping with tradition, we look forward to featuring at least one speaker from each institution or group.

Start of Talks: 11:00 am Saturday
End of Workshop: 5:00 pm Sunday


Location is DSB (David Strong Building) Room C103



Saturday May 4


10:00 Coffee

11:00 "Spectrally Thin Trees" Nick Harvey (UBC)

12:00  "Vertex Sparsifiers"  Konstantin Makarychev (Theory, Microsoft Research)

Lunch 1-2

2:00 "Low Rank Approximation and Regression in Input Sparsity Time" David Woodruff (IBM Almaden)

3:00 "Byzantine Agreement in Polynomial Expected Time" Valerie King  (UVic)


4:15 "Tight Lower Bounds for Greedy Routing in Higher- Dimensional Small-World Grids"  Philipp Woelfel (UCalgary)


Sunday May 5


9:00  "Communication complexity and parallel query processing" Paul Beame (U Washington)

10:00 "Direct Products in Communication Complexity"  Anup Rao (U Washington)


11:15   "Distributed Complexity" Roger Wattenhofer (ETH Zurich/Systems and Networks, Microsoft

Lunch 12:15

1:30  "Rumor spreading and graph expansion" George Giakkoupis (INRIA Rennes)

2:30  "Verifiable Election Technologies," Josh Benaloh (Cryptography, Microsoft Research)


3:45  "Algorithms for Structural Aberration Discovery in Cancer Genomes" Cenk Sahinalp (SFU)

Other Information: 

Transportation to Victoria from Seattle and Vancouver is either by ferry, or more conveniently, by seaplane, from either Vancouver harbour, Vancouver airport (Harbour Air) , or Lake Union in Seattle (Kenmore). If a group coordinates, they may be able to charter their own seaplane for no more than it would cost to fly separately.


Times are chosen to allow seaplane travel: 9:00 am departure from Lake Union in Seattle, and a 6:30 pm departure from Victoria on Sunday.

Good rates at a wide variety of hotels in the downtown area are available through online travel agents if you act now. Buses take about 20 minutes from downtown to the university. Taxis take about 15 minutes and cost about $15.

Recommended inexpensive hotels downtown include:
Parkside Victoria Hotel (very nice, large modern suites), Hotel Rialto (small rooms but otherwise very nice) and Swans Suite Hotel (large, funky, but nice, maybe a bit noisy with a pub downstairs).


PIMS will reimburse speakers and CRG members for reasonable travel costs. We anticipate having some funding for students of CRG members and their institutions. Please contact Sandie Dielissen at to obtain expense forms and if you have questions about  procedures for reimbursement.



This event is part of PIMS CRG 25:  Algorithmic Theory of Networks


Restaurant and other information will be available at