ABSTRACTS
--------------
Thore Husfeldt, ITU,
Title: Fast Zeta Transforms for Lattices with Few Irreducibles
We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size O(vn) for computing the zeta transform and its inverse, thus enabling fast multiplication in the Möbius algebra.
Joint work with Björklund, Kaski, Koivisto, Nederlof, and Parviainen. To appear at SODA 2012.
-------------------------------
Nina Sofia Taslaman, ITU
Title: Shortest Cycle Through Specified Elements
We give a randomized algorithm that finds a shortest simple cycle through a given set of k vertices or edges in an n-vertex undirected graph in time 2^kn^{O(1)}.
Joint work with Björklund and Husfeldt. To appear at SODA 2012.
-------------------------------------
Rasmus Pagh, ITU
Title: Algorithmic Uses of Tabulation Hashing
In several recent papers we have used the special structure of tabulation hashing to achieve polynomial speedups compared to algorithms using a black-box hash function. Applications include estimating the number of vertex pairs connected by a path of length 2,
approximate matrix multiplication, approximating the number of frequent itemsets in a collection of sets, and parallelizing counting of item pairs. The talk will be an overview of these results, explaining the special role of tabulation hashing.
Joint work with Rasmus Resen Amossen, Andrea Campagna, and Konstantin
Kutzkov. Papers appear at RANDOM '10, KDCloud '11, ITCS '12.
-------------------------------
Bengt J. Nilsson, Malmö
"Interior Guarding Monotone Polygons is NP-hard"
The NP-hardness of the art gallery problem for simple polygons has been known since the early 80s. The approximation complexity is still unsolved. For the more restricted monotone polygons it is known that vertex guarding is NP-hard and a constant factor approximation
algorithm for interior guarding exists. We prove that interior guarding monotone polygons is NP-hard. However, the proof does not generalize to APX-hardness so there is still room for improvement.
-------------------------------
Mikkel Thorup, DIKU
"Tabulation Hashing"
Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting of c characters. We initialize c tablesT1,...,Tc mapping characters to random hash codes. A key x=(x1,...,xc) is hashed toT1[x1]⊕⋯⊕Tc[xc], where ⊕ denotes xor. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing. We shall also discuss a twist to simple tabulation that leads to extremely robust performance for linear probing with small buffers.
-------------------------------
Jørgen Bang-Jensen and Alessandro Maddaloni, IMADA, SDU
"The arc-disjoint path problem for generalizations of tournaments"
We prove that for every fixed k there is a polynomial algorithm for deciding the existence of k arc-disjoint paths P_1,P_2,...,P_k with prescribed (not necessarily distinct) endvertices in a digraph which is either quasi-transitive or locally semicomplete. Both of these classes are well-studied and contain the class of tournaments. Our algorithms are based on recent work by Fradkin and Seymour for tournaments and digraphs of bounded indepence number.
-----------------------
Dzmitry Sledneu, Lund
"A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs"
We consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices.
For an n\times n 0-1 matrix C, let K_{C} be the complete weighted graph on the rows of C where the weight of an edge between two rows is equal to their Hamming distance. Let MWT(C) be the weight of a minimum weight spanning tree of K_{C}.
We show that the all-pairs shortest path problem for a directed graph G on n vertices with real weights and adjacency matrix AG can be solved by a combinatorial randomized algorithm in time \widetilde{O}(n^{2}\sqrt {n + \min\{MWT(A_G), MWT(A_G^t)\}}).
As a corollary, we conclude that the transitive closure of a directed graph G can be computed by a combinatorial randomized algorithm in the aforementioned time.
We also conclude that the all-pairs shortest path problem for vertex-weighted uniform disk graphs induced by point sets of bounded density within a unit square can be solved in time \widetilde{O}(n^{2.75})."
Joint work with Andrzej Lingas.
--------------------
Sushmita Gupta, IMADA,
"Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis"
Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis.
In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs that grow with the length of the sequences. Fully characterizing when LRU is strictly better than FIFO is left as an open problem.