Colloquium

Classic error correcting codes are designed to encode messages sent over a noisy channel from one party to another. They are optimized to correct a large number of errors, while still having efficient encoding and decoding algorithms. However, most modern communication is interactive, where two or more parties are actively sending messages based on the information they received. Classic error correcting codes fail to achieve optimal parameters for interactive communication, and in some cases fail to achieve any error correction at all.

The notion of Nash equilibrium (NE) is fundamental to game theory. While a mixed Nash equilibrium is guaranteed to exist in any game, there is no known polynomial-time algorithm for finding one. The tractability of the problem has received much attention in the past decade, in large part due to its theoretical and philosophical significance.

Data-Centers have been emerged in the past few years. Organizations such Google, Microsoft, and Amazon offer different services which are served by their data-centers. In order to provide sufficient and versatile service, commercial data-centers are always researching and developing for better scaling, performance, security, virtualization, management, and topologies.

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with
the goal of obtaining the smallest overhead possible.

The deployment of Formal Methods for Software Engineering, paved the way for a remarkably powerful (Mathematical) analysis at, each stage of the SW Development Process. Indeed, the Mathematics provides us with an adequate level of rigour, not only to precisely Specify & Design SW Systems, but also to meticulously reason about their Properties. This provides a very high level of confidence in the Correctness, Safety and Reliability of the final SW Product.

Statistics in ranked lists plays an important role in analyzing molecular biology measurement data. For example—differential expression analysis yields ranked lists of genes. These ranked lists are analyzed to infer rules and properties. Statistical enrichment methods are of specific interest in this context allowing for the identification of gene sets or sequence elements that are over-represented in the top of measurement derived ranked lists.

Media streaming is among the most popular services provided over the Internet. The lack of a central authority that controls the users, motivates the analysis of Media on Demand (MoD) services using game theoretic concepts. In this work we define and study the corresponding resource-allocation game, where users correspond to self-interested players who choose a MoD server with the objective of minimizing their individual cost. A server provides both storage and broadcasting needs.

Navigating the human genome is currently a 1-dimensional (1D) search: we can find a gene of interest by its coordinates on the linear sequence, along with its annotations and metadata. Graphs are typically used to represent gene associations, for example regulatory interactions, and a large body of research is devoted to reconstruct and analyse such networks in order infer unknown associations. However, 1D genome navigation and association networks typically lack the spatial context in which the underlying biological processes take place.

We consider distance queries in vertex labeled planar graphs. For any fixed $0 < \varepsilon \leq 1/2$ we show how to preprocess a planar graph with vertex labels and edge lengths into a data structure that answers queries of the following form. Given a vertex $u$ and a label $\lambda$ return a $(1+O(\varepsilon))$-approximation of the distance between $u$ and its closest vertex with label $\lambda$.