Student Awards

Kfir Barhum
Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem
Abstract ⇑
In this work, we study the advice complexity of the online minimum Steiner tree problem (ST). Given a (known) graph $G = (V, E)$ endowed with a weight function on the edges, a set of $N$ terminals are revealed in a step-wise manner. The algorithm maintains a sub-graph of chosen edges, and at each stage, chooses more edges from $G$ to its solution such that the terminals revealed so far are connected in it. In the standard online setting this problem was studied and a tight bound of $O(log(N))$ on its competitive ratio is known. Here, we study the power of non-uniform advice and fully characterize it. As a first result we show that using $q•log(|V|)$ advice bits, where $0 ≤ q ≤ N −1$ it is possible to obtain an algorithm with a competitive ratio of $O(log(N/q)$. We then show a matching lower bound for all values of $q$, and thus settle the question.

Maksims Dimitrijevs, Irina Ščeguļnaja, and Rūsiņš Freivalds
Complexity Advantages of Ultrametric Machines
Abstract ⇑
The idea of using p-adic numbers in Turing machines and finite automata to describe random branching of the process of computation was recently introduced. Last year some advantages of ultrametric algorithms were explored. In this paper advantages of time, space and reversal complexity of ultrametric machines are observed.

Luboš Mátl and Tomáš Černý
Effective Manycast Messaging for Overlay Networks
Abstract ⇑
Overlay networks provide various patterns of communication, besides basic unicast, multicast and broadcast patterns that are commonly used in contemporary systems we may find use for anycast messaging that connects sender with one of the closest receivers, based on a given metrics. Such form of communication finds use in content delivery networks or in domain name system. Although there exist domains where multiple of anycast messages are needed at the same time, for example for optimization purposes in content delivery networks, databases or in distributed environment. In this paper, we introduce a novel effective approach to send multiple anycast messages, a manycast, in overlay peer to peer networks. A manycast message aimed for 'n' receivers may although be delivered to multiple identical receivers in the overlay as no preempting mechanism to this exists. Next, we extend the delivery approach to offer distinct manycast receivers. To support our research we conduct a case study in an emulated heterogeneous environment, where we evaluate various communication criteria such as network load, delivery time or number of hops for message delivery. Furthermore, we observe security vulnerability of our approach.