^February March – 2007 ^April

The problem that is addressed in the talk is connecting a collection of agents that are randomly placed in a rectangular area in the plane or 3D space by a wireless network in a way that minimizes the sum of the powers of the agents' transmitters. Depending on a variant, the problem is proved or believed to be NP-hard. Known approximation algorithms use computing means and/or information that is usually not available in practice (e.g., knowledge of the whole network globally available, positions of agents known). Standard power allocation algorithms like unit (uniform) disk model or k-th nearest neighbor graph are provably asymptotically inefficient when applied to a random set of agents

The first result of the talk is a distributed algorithm that provably achieves almost surely a result that is optimal up to a multiplicative constant. However, while being a perfect solution of a problem of constuction of a connected network, a network built by the algorithm mentioned in the previous paragraph is not well suited for communication - it is similar to a minimum spanning tree and hence many physically close pairs of nodes are connected by a very long path in a network (high stretch factor), which causes important congestion in a network. The second part of the talk shows that connectivity of a network can be substantially improved while not increasing the total transmit power too much by inserting a certain number of bridges - direct connections of high stretch factor pairs of nodes.

Algovision is a collection of Java applets for visualization of algorithms. The applets were originally written for an undergraduate course on algorithms at Charles University by the speaker. They cover elementary stuff (tree data structures, heaps, sorting), basic graph algorithms (shortest path, spanning tree, flows), arithmetic algorithms (carry look-ahead addition, FFT), geometric algorithms (convex hull and Voronoi diagram in 2D), string matching (Rabin-Karp, Knuth-Morris-Pratt, Aho-Corasick), and geometric background of the simplex algorithm of LP

Unlike usual algorithm animation applets, Algovision aims to present visual tools to explain the underlying algorithmic idea and invariants that are basis for termination, correctness and complexity analysis; animation and visualization is often used to explain corresponding proofs. Moreover, many Algovision applets present visual tools to show other features of the algorithm in question, e.g., data structures used to implement the algorithm, applications, etc.

We study the $k$-Relaxed Tower of Hanoi Problem $BTH_k(n)$, posed by D. Wood in 1981. It differs from the classical problem by the relaxed placement rule: a larger disk can be placed above a smaller one if their size difference is less than $k$. The shortest sequence of moves from the standard state of disks $[1..n]$ on peg A to that on peg C, using peg B, is in question. For $k=1$ we get the classical problem.

In 1992, D. Poole suggested a solution for this problem, which is now known to have a fundamental gap. Beneditkis, Berend, and Safro suggested in 1998 a sequence of moves, denoted by $\AA_k(n)$, and for the case $k=2$ proved its optimality for $BTH_k(n)$.

We prove optimality of $\AA_k(n)$ for $BTH_k(n)$, for the general $k$. (Interestingly, a proof of optimality of $\AA_n$ for $BTH_n$ was suggested independently by Xiaomin Chen et al., approximately at the same time.)

We also survey some related problems: 1. Finding an optimal move sequence for $BTH_k(n)$, when allowing the sizes of the $n$ disks be any set of $n$ distinct integers. 2.a Finding the diameter of the configuration graph of $BTH_k(n)$. 2.b Finding the average distance between nodes in the configuration graph of $BTH_k(n)$. 3. Finding the family of all optimal solutions for $BTH_k(n)$ and their number.

If time permits, we would survey some related open problems.
In joint work with Yefim Dinitz.

We shall talk about three topics in which there has been recent progress. First, PageRank, the key idea behind Google, has been modified to involve a "teleport set," leading to the ability to measure importance of Web pages according to their relevance to a specific topic. The concept may also lead to methods for detecting spam pages. Second, a number of problems involving massive data are solved using a pair of "hashing" techniques together: minhashing and locality-sensitive hashing. We shall explain how these work and how they are used, for example, to find similar Web pages. Finally, we look at the classic problem of frequent itemsets in market baskets ("what to people buy together?"). The a-priori algorithm can be improved by careful attention to how main memory is managed

We consider broadcasting in radio networks, modeled as unit disk graphs (UDG). Network stations are modeled as points in the plane, where a station is connected to all stations at Euclidean distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning.

It turns out that the running time of deterministic broadcasting algorithms depends on two parameters of the UDG network, namely, its diameter $D$ and its granularity $g$, which is the inverse of the minimum Euclidean distance between any two stations. We present a deterministic broadcasting algorithm which works in time $O(D g)$ under the conditional wake up model. On the negative side, we prove that any deterministic algorithm requires $\Omega(D \sqrt{g})$ time to accomplish broadcasting. For the spontaneous wake up model, we establish a lower bound of $\Omega(\min\{D + g^2, D \log{g}\})$ on deterministic broadcasting time and prove that this is tight. Thus our results yield a provable separation between the two models: for some parameter values, the lower bound in the first model is significantly larger than the upper bound in the second.

Recent research on shared-memory blocking algorithms (such as mutual exclusion and leader election algorithms) focuses on local-spin algorithms, in which processes busy-wait on locally-accessible variables. The most widely used metric for analyzing the time-complexity of such algorithms is the remote-memory-references (RMRs) metric, which counts the number of non-local accesses performed by processes.

While there is a lower bound of $\Omega(\log n / \log \log n)$ RMRs on the worst-case complexity of mutual exclusion algorithms that use only read/write operations, it was unknown whether such a lower bound applied also for the leader election problem, which may be regarded as `one-shot' mutual exclusion.

We provide a negative answer to this question by presenting an $O(1)$ RMRs leader election algorithm, using reads/writes only, improving on $\Theta(\log n)$ best prior-art algorithms. We show that our technique can be extended for deriving constant RMRs implementations of synchronization primitives that are considered stronger, such as consensus and comparison primitives (e.g., the widely used compare-and-swap).

Herlihy has shown that synchronization primitives vary widely in their power to support wait-free implementations and classified them in the wait-free hierarchy based on this computability power . For blocking implementations, this hierarchy is flat, since all primitives can be implemented in a blocking manner from reads and writes. Instead of comparing the computability power of a pair of primitives, it is therefore natural to ask whether we can base such a comparison on the RMR complexities of implementing these primitives from reads and writes. Our results establish that looking at the relative power of primitives through this lens reveals a landscape sharply different from that of Herlihy's wait-free hierarchy.

This talk is for a general audience and, to the extent possible, will be self-contained.

Joint work with Wojciech Golab, Vassos Hadzilacos, and Philipp Woelfel.