Summer School on Randomized Techniques for Combinatorial Algorithms

This Summer School is organized by the PIMS CRG: Algorithmic Theory of Networks: 2012-2015

The lessons will take place in the TASC Building, Burnaby Campus, room T 9204. Campus map.

Registration fee : Registration for this event is now closed. Please contact petra@sfu.ca if you have any querries.

Hotels/Accomodation:

Ramada Coquitlam, Best Western Coquitlam and Hosteling International hostel.

To go from the airport to SFU you can take a taxi or the SkyTrain via downtown Vancouver.


 

Survey:

Please help PIMS to improve the quality of its events and plan for the future by filling out this quick and painless survey.

Full scientific report available here.  

  Sublinear Algorithms

• Robert Elsasser, University of Salzburg

   Random Walks and Their Applications in Algorithms

Random walks on graphs play an important role in different scientific fields. In the standard version, at the beginning a particle is situated on a vertex of a given graph. In each time step, the particle moves from its current node to a neighbor chosen uniformly at random. Measures of interest we consider are the mixing time, i.e., how fast the random walk converges to its limiting distribution, and the cover time, i.e., the expected number of steps needed to visit all vertices - maximized over all starting nodes. We will go over several applications of random walks in the theory of algorithms, such as network exploration and distributed voting. We will also consider a number of modifications of the standard version, which allow us to design efficient algorithms for the applications mentioned above.

• Nick Harvey, UBC

   Concentration bounds for sums of random variables and matrices

1) Chernoff bounds
3) Talagrand's Inequality
4) Scalar concentration bounds for negatively dependent random variables
5) Pipage rounding
6) Basic concentration for random matrices
7) Tropp's inequality for concentration of random matrices 

•  Seffi Naor, Technion

    Randomized Algorithms: Recent Results and Techniques

Randomization has evolved by now into a very useful toolbox which is successfully applied to many combinatorial problems. We will present and discuss recent applications of randomization to diverse areas such as maximizing submodular functions, design and analysis of competitive online algorithms, and partitionings of graphs.

•  Eli Upfal, Brown University

    The Monte Carlo Method

The Monte Carlo method refers to a collection of tools for estimating
values through sampling and simulation. In this class we'll cover the basic Monte Carlo method, discuss its limitation in estimating sparse values, and then study the Monte Carlo Markov chain method that provides a partial solution to this difficulty.