Speaker: Pawel Lorek (Universiy of Wroclaw, Poland)
Title: Duality for Mobius monotone Markov chains
Date and location: March 18, 2pm, salle rose

Speaker: Sergey Foss (Heriot-Watt University, Edinburgh and Institute of Mathematics, Novosibirsk)
Title: Adaptive transmission protocols for a random multiple access channel
Date and location: June 11, 11am, Salle du conseil
Abstract: There are known two "ALOHA-type" models, (a) with a finite number of queues and with messages ahead of each queue being potentially "active", and (b) without queues and all "active" messages. I'll talk about model (b), introduce a number of new protocols for their stability, and discuss some open problems.

Speaker: Venkat Anantharam (University of California, Berkeley)
Title: Convex relative entropy decay in Markov chains
Date and location: June 11, 3:30pm, Salle du conseil
Abstract: (Joint work with Varun Jog.) Consider an irreducible continuous time Markov chain with a finite or a countably infinite number of states and admitting a unique stationary probability distribution. The relative entropy of the distribution of the chain at any time with respect to the stationary distribution is a monotonically decreasing function of time. It is interesting to ask if this function is convex. We discuss this question for finite Markov chains and for Jackson networks, which are a class of countable state Markov chains of interest in modeling networks of queues.

Speaker: Djalil Chafaï (Université Paris-Dauphine and Institut Universitaire de France)
Title: About non-Hermitian random matrices
Date and location: July 8, 2pm, Salle du conseil
Abstract: This accessible talk will present the essentials of the spectral analysis of non Hermitian random matrices.

Speaker: Nidhi Hegde (Technicolor)
Title: Self-organizing Flows in Social Networks
Date and location: September 23, 2pm, Salle du conseil (4th floor)
Abstract: Online social networks offer users new means of accessing information, essentially relying on "social filtering", i.e. propagation and filtering of information by social contacts. The sheer amount of data flowing in these networks, combined with the limited budget of attention of each user, makes it difficult to ensure that social filtering brings relevant content to interested users. Here we are interested in measuring to what extent self-organization of a social network results in efficient social filtering.
To this end we introduce flow games, a simple abstraction that models network formation under selfish user dynamics, featuring user-specific interests and budget of attention. In the context of homogeneous user interests, we show that selfish dynamics converge to a stable network structure (namely a pure Nash equilibrium) with close-to-optimal information dissemination. We show that, in contrast, for the more realistic case of heterogeneous interests, selfish dynamics may lead to information dissemination that can be arbitrarily inefficient, as captured by an unbounded "price of anarchy".
Nevertheless the situation differs when user interests exhibit a particular structure, captured by a metric space with low doubling dimension. In that case, natural autonomous dynamics converge to a stable configuration. Moreover, users obtain all the information of interest to them in the corresponding dissemination, provided their budget of attention is logarithmic in the size of their interest set.

Speaker: Kuang Xu (Microsoft Research)
Title: On the power of (even a little) Flexibility in Dynamic Resource Pooling
Date and location: October 21, 10am, Salle du conseil (4th floor)
Abstract: It is well known that resource pooling (or, equivalently, the use of flexible resources that can serve multiple types of requests) significantly improves the performance of service systems. On the other hand, complete resource pooling often results in higher infrastructure (communication and coordination) costs. This leads us to explore the benefits that can be derived by a limited amount of resource pooling, and the question whether a limited amount of pooled resources can deliver most of the benefits of complete resource pooling. Applications in large-scale server farms, skill-based call centers, health care, and flexible supply chains are among our main motivations.
We demonstrate, in the context of some concrete models, that a very small amount of flexibility can be surprisingly powerful in improving performance, both in terms of queueing delay and system capacity. However, to harness the benefits of flexibility, one should carefully architect network topologies, scheduling policies, and how to properly leverage (predictive) information in making dynamic resource allocation decisions. In this talk, I will discuss stochastic models and analytical results that provide interesting insights on these challenges.
Based on joint work with Carri W. Chan, Joel Spencer, Madhu Sudan, and John N. Tsitsiklis.

Speaker: Fabio Cecchi (Eindhoven University of Technology)
Title: Throughput of CSMA Networks with Buffer Dynamics.
Date and location: November 20, 10am, Salle du conseil (4th floor)
Abstract: Random-access algorithms such as the Carrier-Sense Multiple-Access (CSMA) protocol provide a popular mechanism for distributed medium access control in large-scale wireless networks. In recent years fairly tractable models have been shown to yield remarkably accurate throughput estimates in scenarios with saturated buffers. In contrast, in non-saturated scenarios, where nodes refrain from competition for the medium when their buffers are empty, a complex two-way interaction arises between the activity states and the buffer contents of the various nodes. As a result, the throughput characteristics in such scenarios have largely remained elusive so far. We provide a generic structural characterization of the throughput performance and corresponding stability region in terms of the individual saturation throughputs of the various nodes. While the saturation throughputs are difficult to explicitly determine in general, we identify certain cases where these values can be expressed in closed form. In addition, we demonstrate that various lower-dimensional facets of the stability region can be explicitly calculated as well, depending on the neighborhood structure of the interference graph.