Calendar

(ACM EC 2019 Best Full Paper Award)

A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1,..., Xn drawn independently from a distribution F, the goal is to choose a stopping time τ so as to maximize α such that for all distributions F we have E[Xτ] ≥ α · E[maxt Xt]. What makes this problem challenging is that the decision whether τ = t may only depend on the values of the random variables X1,..., Xt and on the distribution F. For a long time the best known bound for the problem had been α ≥ 1 − 1/e ≈ 0.632, but quite recently a tight bound of α ≈ 0.745 was obtained. The case where F is unknown, such that the decision whether τ = t may depend only on the values of the random variables X1,..., Xt, is equally well motivated but has received much less attention. A straightforward guarantee for this case of α ≥ 1/e ≈ 0.368 can be derived from the solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from F , and show that even with o(n) samples α ≤ 1/e. On the other hand, n samples allow for a significant improvement, while O(n2) samples are equivalent to knowledge of the distribution: specifically, with n samples α ≥ 1 − 1/e ≈ 0.632 and α ≤ ln(2) ≈ 0.693, and with O(n2) samples α ≥ 0.745 − ϵ for any ϵ > 0.

Joint work with Jose Correa (Universidad de Chile), Felix Fischer (Queen Mary), and Kevin Schewior (ENS Paris)

Understanding and improving the performance of applications on NUMA systems

Modern multicore systems are based on a Non-Uniform Memory Access (NUMA) design. Efficiently exploiting such architectures is notoriously complex. In this talk we will present different works we did during these last years to help application and system designers leveraging the power of these architectures. In particular, we will present some profiling tools that we used to detect inefficiencies and some algorithms/heuristics that we implemented within the Linux kernel to improve the performance of NUMA systems.

Bruno will present his report from the new trends he saw this year at supercomputing as well as explain some technical talks he liked presented at the conference.