Random Graphs and Large Networks 
Dimitris Achlioptas, UC Santa Cruz & RACTI
Abstract: The bestknown model of random graphs was introduced 50 years ago, by Erdos
and Renyi (ER): take n vertices and connect each pair of them, independently,
with probability p(n). By now, and thousands of research papers later, we
know that ER random graphs have a number of amazing properties, many of which
we understand very well. A bit more slowly we have also come to understand
that ER random graphs can be poor models of "network realities": it is
impossible to place the vertices of a (typical) ER random graph in a
lowdimensional space, so that for each pair of vertices, their geometric
distance is a good approximation of their graphical (shortestpath) distance.
In other words, ER random graphs are inherently highdimensional objects, in
contrast to many real networks. In this tutorial talk we will survey some of
the fundamental results for ER random graphs and use them as springboards to
introduce (and compare with) alternative random graph models.

Scheduling in server farms: approaches and open problems 
Mor HarcholBalter, Carnegie Mellon University
Abstract: Server farms are ubiquitous in applications ranging from Web server farms to highperformance supercomputing systems to call centers. The popularity of the server farm architecture is understandable, as it allows for increased performance, while being costeffective and easily scalable, allowing applications to meet response time goals and power goals.
Given the prevalence of server farms, it is surprising that even at this late date so little is understood with respect to designing policies for resource management in multiserver systems. In this talk we address the following design questions:
 What are good policies for routing/dispatching jobs to hosts in a server farm?
 How should jobs be scheduled at the individual hosts?
 How can we choose policies to combat job size variability?
 What are the tradeoffs between response time and fairness goals?
 How can policies simultaneously meet response time goals and energy goals for a server farm?
There are at least three distinct communities studying scheduling in server farms from an analytical perspective. These include the SIGMETRICS community, the INFORMS community, and the SPAA/STOC/FOCS community, all of which have different approaches and goals. One of our goals in this tutorial is to make researchers aware of results in these different communities. The emphasis will be on intuition, so that the talk is accessible to newcomers as well as oldtimers. In surveying the newest results, we will also present some practical open problems.

Fundamentals of Continuum Percolation 
Mathew Penrose, University of Bath
Abstract: We consider graphs created on a randomly scattered set of vertices in Euclidean dspace, by placing an edge between any two vertices at most unit distance apart. When the underlying set of vertices is an infinite homogeneous Poisson process, this graph is called the Gilbert graph; when it is a finite set of points in a cube, it is called the random geometric graph. We discuss basic notions notions for the Gilbert graph such as cluster size distribution, and phase transition for infinite components. We also relate these notions to asymptotic properties of the random geometric graph.

Multisource Network Coding 
Raymond W. Yeung, Chinese University of Hong Kong
Abstract: The capacity of network coding for a single source has the nice and sweet maxflow mincut characterization. Once we move beyond singlesource, the problem becomes much more difficult. The capacity region for multisource network coding on acyclic networks was completely characterized by Yan, Yeung, and Zhang (2007) in terms of $\Gamma^*$, the region of all entropy functions. This characterization is strongly tied to the study of nonShannontype inequalities. In this tutorial, we will first explain this characterization on an intuitive basis. This characterization, however, works only for block network codes with arbitrarily small probability of decoding error but does not work with variablerate network codes that can possibly achieve zero error. In the rest of the tutorial, we will explain the hurdles involved and report some of our latest efforts toward overcoming these hurdles.
