Summer School on Randomized Techniques for Combinatorial Algorithms
- Start Date: 08/18/2014
- End Date: 08/22/2014
• 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.
Simon Fraser University
Teaching is from 9:30-12:00 and from 13:30 to 16:00 every day.
Monday: Nick Havey
Tuesday: Seffi Naor
Wednesday: Eli Upfal
Thursday: Artur Czumaj
Friday: Robert Elsaesser
*The length of the courses might be variable, possibly ending later than scheduled.
*Coffee breaks will be provided, but students will be responsible for their own lunches.
There is some funding available; to apply please e-mail Petra Berenbrink
This Summer School is organized by the PIMS CRG: Algorithmic Theory of Networks: 2012-2015
Registration fee is $50 (for coffee breaks), registration is open: Sign up below.
Please help PIMS to improve the quality of its events and plan for the future by filling out this quick and painless survey.
Please login with PIMS then return to this event page and click the "Sign Up" button.