09:00 to 09:50 Registration 09:50 to 10:00 Welcome by John Toland, Director of the Institute INI 1 10:00 to 10:45 PH Robert (INRIA Paris - Rocquencourt)On the Fluid Limits of a Resource Sharing Algorithm with Logarithmic Weights The properties of a class of resource allocation algorithms for communication networks are presented in this talk.The algorithm is as follows: if a node of this network has x requests to transmit, then it receives a fraction of the capacity proportional to log(x), the logarithm of its current load. A fluid scaling analysis of such a network is presented. It is shown that several different times scales play an important role in the evolution of such a system. An interesting interaction of time scales phenomenon is exhibited. It is also shown that these algorithms with logarithmics weights have remarkable, unsual, fairness properties. A heavy traffic limit theorem for the invariant distribution is proved. Joint work with Amandine Veber. INI 1 10:45 to 11:00 Morning Coffee 11:00 to 11:45 D Shah (Massachusetts Institute of Technology)Optimal queue-size scaling in switched networks We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input- queued switches, wireless networks and more recently data-centers. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. Designing a scheduling policy with optimal average queue-size for switched network has been a question of interest for a while now. As the main result, we shall discuss a new class of online scheduling policies that achieve optimal scaling for average queue-size for a class of switched networks including input-queued switches. Talk is based on work with Neil Walton (U of Amsterdam)+ Yuan Zhong (UC Berkeley). INI 1 12:30 to 13:30 Lunch at Wolfson Court 13:30 to 14:15 AR Ward (University of Southern California)Routing and Staffing to Incentivize Servers in Many-Server Systems Co-authors: S. Doroudi, R. Gopalakrishnan, and A. Wierman Traditionally, research focusing on the design of scheduling and staffing policies for service systems has modeled servers as having fixed (possibly heterogeneous) service rates. However, service systems are often staffed by people. Then, the rate a server chooses to work may be impacted by the scheduling and staffing policies used by the system. We present a model for such strategic servers'' that choose their service rate in order to maximize a trade-off between an effort cost'', which captures the idea that servers exert more effort when working at a faster rate, and a value of idleness'', which assumes that servers prefer to be idle as much as possible. In this strategic server framework, we re-visit classic scheduling and staffing questions in many-server systems, and, in particular, we investigate the performance of the common square-root safety staffing rule. INI 1 14:15 to 14:30 Afternoon Tea 14:30 to 15:15 AN Rybko (Russian Academy of Sciences)Infinite Networks with Varying Topology - A Mean-Field Approach We consider a model of a queuing network, containing infinite moving servers (nodes). The customers of different types are getting into the network in corresponding entrance nodes and each of the customer c has an exit node D(c) which it needs to reach. On the way to its destination the customer visits some intermediate nodes, where it stays in queues. Service times distributions depend on the customer and on the node types. After being served at any node v, the customer c is sent to the server v' which is the closest to the destination server D(c). Once it gets to D(c), it leaves the network. The main feature of the network is that its nodes are moving. So while the customer c is waiting in the queue in some node v, this node and its destination node D(c) can move. In such networks with moving nodes new effects take place, which are encountered in the situation with stationary nodes. My talk is based on joint paper with Francois Baccelli and Senya Shlosman. Its main result can be described as follows: we start with the definition of the class of the networks with jumping nodes. The network can be finite or infinitely extended. In order to be able to treat them we consider the mean-field version of it, which consists of N copies of the network, interconnected in a mean-field manner. We show that as N increases, the limiting object becomes Non-Linear Markov Process in time. We establish the existence of the NLMP and the convergence to it. INI 1 17:00 to 18:00 Welcome reception
 10:00 to 10:45 A Anandkumar (University of California, Irvine)A Tensor Spectral Approach to Learning Mixed Membership Community Models Co-authors: Rong Ge (Princeton), Daniel Hsu (Microsoft Research), Sham Kakade (Microsoft Research) Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al. 2008. This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebra operations, e.g. singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model. Related Links: http://newport.eecs.uci.edu/anandkumar/pubs/AnandkumarCommunity.pdf - manuscript INI 1 10:45 to 11:00 Morning Coffee 11:00 to 11:45 V Borkar (Indian Institute of Technology)Miscellaneous gossip This talk will describe several problems related to gossip and related algorithms implemented on a network. These include: convergence issues for averaging schemes on graphs and a learning' variant, distributed ranking algorithms on graphs, opinion dynamics on graphs and its optimization and/or control, etc. INI 1 12:30 to 13:30 Lunch at Wolfson Court 13:30 to 14:15 M Olvera-Cravioto (Columbia University)Ranking algorithms on directed random networks The probabilistic analysis of information ranking algorithms on directed random networks, e.g., Google's PageRank, has recently led to natural approximations based on stochastic fixed-point equations whose explicit solutions can be constructed on weighted branching trees and whose tail behavior can be described in great detail. In this talk we present a model for generating directed random graphs with prescribed degree distributions where we can prove that the rank of a randomly chosen node does indeed converge to the solution of the corresponding fixed-point equation as the number of nodes in the graph grows to infinity. The proof of this result is based on classical random graph coupling techniques combined with the now extensive literature on the behavior of branching recursions on trees. The results we present are applicable to a wide class of linear algorithms on directed graphs, and have the potential to be extended to other max-plus type of recursions. This is joint work with Ningyuan Chen and Nelly Litvak. INI 1 14:15 to 14:30 Afternoon Tea 14:30 to 15:15 B Prabhakar (Stanford University)Models of congestion and human response INI 1 15:45 to 17:00 Open Problems Session INI 1 17:00 to 18:30 Poster Session
 10:00 to 10:45 R van der Hofstad ([TU Eindhoven])Optimal flows on random graphs We investigate minimal-weight problems on the configuration model, in which flow passes through the network minimizing the total weight along edges. In practice, one is both interested in the actual weight of the minimal weight path, which represents its cost, as well as the number of edges used or hopcount, as this is often a good measure of the delay observed in the network. We assume that the edge weights are independent continuous random variables, leading to first passage percolation on the configuration model. We then investigate the total weight and hopcount of the minimal weight path. We study how the minimal weight and hopcount depend on the structure of the edge weights as well as on the structure of the graph. Our proofs crucially rely on the connection between first passage percolation and continuous-time branching processes, which is due to the tree-like nature of the configuration model. The above research is inspired by transport in real-world networks, such as the Internet. Measurements have shown fascinating features of the Internet, such as the small world phenomenon'. The small-world phenomenon states that typical distances in the network under consideration is small. Also, the degrees in the Internet are rather different from the degree structure in classical random graphs. Internet is a key example of a complex network, other examples being the Internet Movie Data Base, social networks, biological networks, the WWW, etc. [This is joint work with Gerard Hooghiemstra, Shankar Bhamidi, Piet Van Mieghem, Henri van den Esker and Dmitri Znamenski.] INI 1 10:45 to 11:00 Morning Coffee 11:00 to 11:45 J Salez (Université Paris 7 - Denis-Diderot)Distances in large random regular networks We study the array of point-to-point distances in large random regular graphs equipped with exponential edge-lengths. The asymptotic marginal distribution of a single entry is now well-understood, thanks to the work of Bhamidi, van der Hofstad and Hooghiemstra (2010). In this talk, we will show that the whole array, suitably recentered, converges in the weak sense to a rather simple infinite random array. This confirms a prediction of David Aldous. INI 1 12:30 to 13:30 Lunch at Wolfson Court 13:30 to 14:15 AE Holroyd (Microsoft Research)Self-organizing cellular automata Cellular automata display an extraordinary range of behavior, ranging from the very simple to the apparently chaotic, with many cases in between. Perhaps the most interesting rules are those that yield multiple behavior types from different initial conditions - this is common even for one-dimensional rules started from finitely-supported seeds. If a rule yields chaos from some initial conditions, it is tempting to conclude by analogy with the second law of thermodynamics that chaos should be prevalent from almost all initial conditions. For a certain natural class of rules, we prove that the opposite holds: typical (i.e. random) initial seeds self-organize into predictable (but non-trivial) evolution, while exceptional seeds generate more complicated behavior, including chaos. The key technique is the application of percolation arguments to the highly non-independent setting of space-time configurations of cellular automata. Joint work with Janko Gravner. INI 1 14:15 to 14:30 Afternoon Tea 14:30 to 15:15 JB Martin (University of Oxford)Forest fires and coagulation-deletion processes Consider the following extension of the Erdos-Renyi random graph process; in a graph on $n$ vertices, each edge arrives at rate 1, but also each vertex is struck by lightning at rate $\lambda$, in which case all the edges in its connected component are removed. Such a "mean-field forest fire" model was introduced by Rath and Toth. For appropriate ranges of $\lambda$, the model exhibits self-organised criticality. We investigate scaling limits, involving a multiplicative coalescent with an added "deletion" mechanism. I'll mention a few other related models, including epidemic models and "frozen percolation" processes. INI 1 15:45 to 17:00 Open Problems Session INI 1 17:00 to 18:30 Poster Session
 10:00 to 10:45 M Mandjes (Universiteit van Amsterdam)Timescaling results for Markov modulated infinite-server systems and OU processes Co-authors: J. Blom (CWI), K. de Turck (Ghent), O. Kella (Jerusalem), D. Anderson (Wisconsin), H. Thorsdottir (CWI), G. Huang (Amsterdam), P. Spreij (Amsterdam) In this talk I'll consider an infinite-server queue whose input is modulated by a Markovian background process, with a focus on the analysis of the number of customers in the system, both in the central-limit and the large deviations regime. In the scaling that we study, the background process is sped up by a factor N^f, while the arrival rate are scaled by N. Interestingly, in the CLT regime crucially different results come out for f > 1 and for f INI 1 10:45 to 11:00 Morning Coffee 11:00 to 11:45 J Blanchet (Columbia University)Tolerance Enforced Simulation for Stochastic Differential Equations via Rough Path Analysis Consider a stochastic differential equation (SDE) driven by Brownian Motion which possesses a strong solution in the interval [0,t]. Given any tolerance error, say epsilon, defined in advance, we explain how to simulate a piece-wise linear path which approximates the underlying SDE in uniform norm in [0,t] with an error less than epsilon with probability one. The technique, as we shall explain, takes advantage of continuity estimates, studied in the theory of rough paths, of the Ito-Lyons map defining the underlying the SDE. (This presentation is based on joint work with Xinyun Chen and Jing Dong.) INI 1 12:30 to 13:30 Lunch at Wolfson Court 13:30 to 14:15 A Ganesh (University of Bristol)On the secure connectivity of wireless sensor networks We consider a model of a wireless sensor network in which nodes are distributed uniformly at random over a unit square, and can communicate other nodes within a ?xed radius. This is the well-known random geometric graph model. In addition, each node is assigned a subset of cryptographic keys chosen uniformly at random from a key pool. Two nodes can communicate only if they are within range of each other, and possess at least one common key. We establish a connectivity threshold for these random graph models. This resolves a conjecture of Osman Yagan. Joint work with Bikash Dey, Santhana Krishnan and D. Manjunath. INI 1 14:15 to 14:30 Afternoon Tea 14:30 to 15:15 H Thorisson (University of Iceland)Unbiased shifts of Brownian Motion Let $B = (B_t)_{t\in\mathbb{R}}$ be a two-sided standard Brownian motion. Let $T$ be a measurable function of $B$. Call $T$ an \emph{unbiased shift} if $(B_{T+t}-B_T)_{t\in\mathbb{R}}$ is a Brownian motion independent of $B_T$. We characterize unbiased shifts in terms of allocation rules balancing local times of $B$. For any probability distribution $\nu$ on $\mathbb{R}$ we construct a nonnegative stopping time $T$ with the above properties such that $B_T$ has distribution $\nu$. In particular, we show that if we travel in time according to the clock of local time at zero we always see a two-sided Brownian motion. A crucial ingredient of our approach is a new theorem on the existence of allocation rules balancing jointly stationary diffuse random measures on $\mathbb{R}$. We also study moment and minimality properties of unbiased shifts. INI 1