Contributions to structural communication complexity, 2009. - Online-Ressource (PDF-Datei: 91 S., 740 KB) Ilmenau : Techn. Univ., Diss., 2009
In der Dissertation werden strukturelle Probleme in Yaos Kommunikationsmodell untersucht, die sich thematisch drei Bereichen dieses Gebietes zuordnen lassen: Der erste Teil der Arbeit beschäftigt sich mit dem fundamentalen Problem der Herleitung unterer Schranken für die randomisierte Kommunikationskomplexität. Hauptergebnis ist die folgende Charakterisierung, die auch als nicht-triviale Verallgemeinerung von Shannons "Noiseless Coding Theorem" angesehen werden kann: die durchschnittliche deterministische Informationskomplexität stimmt bis auf einen konstanten Faktor mit der durchschnittlichen deterministischen Kommunikationskomplexität überein, und zwar für jede Funktion und jede Verteilung auf den Eingaben. Ein weiteres Ergebnis sind untere Schranken für die public coin Las Vegas Kommunikationskomplexität, die um einen konstanten Faktor besser sind, als die bis dahin bekannten. Der zweite Teil beschäftigt sich mit der 30 Jahre alten PH-vs.-PSPACE-Frage in der Kommunikationskomplexität. Wir übertragen dazu die Todaschen Sätze aus der klassischen Komplexitätstheorie in Yaos Modell und entwickeln ein Maß für die Klasse BP-Parität-P, denapproximativen GF(2)-Rang. Über eine enge Beziehung zu dem Konzept"matrix rigidity" erhalten wir ein Maßkonzentrationsresultat: die meisten Funktionen haben eine fast lineare BP-Parität-P-Komplexität. Wir entwickeln außerdem ein Protokoll für die innere Produktfunktionmod 2 mit wenigen Alternierungen. Dies könnte darauf hinweisen, dass die Klasse BP-Parität-P "klein" ist im Vergleich zu PSPACE. Des Weiteren leiten wir für auf dünnen quasi-zufälligen Graphfamilien basierenden Adjazenzproblemen eine hohe Parität-P-Komplexität her, die dem Logarithmus des Kehrwerts der Kantendichte entspricht. Im dritten Teil untersuchen wir Überdeckungsstrukturgraphen. Diese sind definiert als Schnittgraphen von maximalen monochromatischen Untermatrizen einer Matrix. Wir zeigen, dass nicht jeder Graph ein Überdeckungsstrukturgraph ist. Danach betrachten wir die Teilklasseder "schönen" Graphen und charakterisieren schöne quadratfreie bipartite und schöne Kantengraphen quadratfreier bipartiter Graphen.
http://www.db-thueringen.de/servlets/DocumentServlet?id=14685
Experimental variations of a theoretically good retrieval data structure. - In: Algorithms - ESA 2009, (2009), S. 742-751
A retrieval data structure implements a mapping from a set S of n keys to range R={0,1}^r , e.g. given by a list of key-value pairs (x,v)?S×R, but an element outside S may be mapped to any value. Asymptotically, minimal perfect hashing allows to build such a data structure that needs n*log_2(e)+nr+o(n) bits of memory and has constant evaluation time. Recently, data structures based on other approaches have been proposed that have linear construction time, constant evaluation time and space consumption O(nr) bits or even (1+?)nr bits for arbitrary ?>0. This paper explores the practicability of one such theoretically very good proposal, bridging a gap between theory and real data structures.
http://dx.doi.org/10.1007/978-3-642-04128-0_66
Hash, displace, and compress. - In: Algorithms - ESA 2009, (2009), S. 682-693
A hash function h, i.e., a function from the set U of all keys to the range range [m]={0,...,m-1} is called a perfect hash function (PHF) for a subset S?U of size n?m if h is 1-1 on S. The important performance parameters of a PHF are representation size, evaluation time and construction time. In this paper, we present an algorithm that permits to obtain PHFs with expected representation size very close to optimal while retaining O(n) expected construction time and O(1) evaluation time in the worst case. For example in the case m=1.23n we obtain a PHF that uses space 1.4 bits per key, and for m=1.01n we obtain space 1.98 bits per key, which was not achievable with previously known methods. Our algorithm is inspired by several known algorithms; the main new feature is that we combine a modification of Pagh's hash-and-displaceъ approach with data compression on a sequence of hash function indices. Our algorithm can also be used for k-perfect hashing, where at most k keys may be mapped to the same value.
http://dx.doi.org/10.1007/978-3-642-04128-0_61
Perfect hashing for state spaces in BDD representation. - In: KI 2009: advances in artificial intelligence, (2009), S. 33-40
http://dx.doi.org/10.1007/978-3-642-04617-9_5
Brief announcement: tight lower bounds for greedy routing in uniform small world rings. - In: Proceedings of the 2009 ACM Symposium on Principles of Distributed Computing, (2009), S. 300-301
Motivated by Kleinberg's Small World Graph model and packet routing strategies in peer-to-peer networks, greedy routing algorithms on augmented networks have been investigated thoroughly. We prove tight lower bounds for one- and two-sided greedy routing on augmented rings.
Tight lower bounds for greedy routing in uniform small world rings. - In: Proceedings of the 2009 ACM International Symposium on Theory of Computing, (2009), S. 591-600
We consider augmented ring-based networks with vertices 0,...,n-1, where each vertex is connected to its left and right neighbor and possibly to some further vertices (called long range contacts). The outgoing edges of a vertex v are obtained by choosing a subset D of {1,2,...n-1}, with 1, n-1 in D, at random according to a probability distribution mu on all such D and then for each i in D connecting v to (v+i) mod n by a unidirectional link. The choices for different v are done independently and uniformly in the sense that the same distribution mu is used for all v. The expected number of long range contacts is l=E(|D|)-2. Motivated by Kleinberg's (2000) Small World Graph model and packet routing strategies for peer-to-peer networks, the greedy routing algorithm on augmented rings, where a packet sitting in a node v is routed to the neighbor of v closest to the destination of the package, has been investigated thoroughly, both for the "one-sided case", where packets can travel only in one direction, and the "two-sided case", where there is no such restriction. In this paper, for both the one-sided and the two-sided case and for an arbitrary distribution mu, we prove a lower bound of Omega((log n)2/l) on the expected number of hops that are needed by the greedy strategy to route a package between two randomly chosen vertices on the ring. This bound is tight for Omega(1)<=l=O(log n).
Applications of a splitting trick. - In: Automata, languages and programming, (2009), S. 354-365
We study applications of a simple method for circumventing the "full randomness assumption" when building a hashing-based data structure for a set S of keys. The general approach is to "split" S into "pieces" S_i , by a splitting hash function. On a piece S_i, a method or data structure for generating full randomness is used that uses more space than |S_i|. Under certain circumstances, this data structure can be "shared" among the constructions for the pieces S_i , which leads to a tighter overall space bound. The method was introduced in the context of cuckoo hashing and its variants, but it seems to have wider applicability. To demonstrate its power and some subtleties, we study three new applications, improving previous constructions: (i) Space-efficient simulation of full randomness on S (following work by Pagh and Pagh (2003/08) and Dietzfelbinger and Woelfel (2003)); (ii) Construction of highly independent functions in the style of Siegel (1989/2004); (iii) One-probe schemes as in work by Buhrman, Miltersen, Radhakrishnan, and Venkatesh (2000/02) and Pagh and Pagh (2002).
http://dx.doi.org/10.1007/978-3-642-02927-1_30
On risks of using a high performance hashing scheme with common universal classes, 2009. - Online-Ressource (PDF-Datei: 81 S., 868 KB) : Ilmenau, Techn. Univ., Diss., 2009
Parallel als Druckausg. erschienen
Der Beitrag dieser Dissertation ist die mathematische Analyse eines Hashing-Verfahrens namens Cuckoo Hashing in Kombination mit einfachen, effizient auswertbaren Funktionen zweier Hashklassen, die wir die multiplikative Klasse bzw. die lineare Klasse nennen. Cuckoo Hashing hat die deutliche Tendenz, mit Funktionen dieser beiden Klassen schlecht zu funktionieren. Um dies zu beweisen, untersuchen wir den Einfluss der inneren Struktur solcher Funktionen auf das Verhalten des Cuckoo-Verfahrens, wenn der Versuch unternommen wird, eine Schlüsselmenge S in anfangs leere Tabellen einzufügen. Cuckoo Hashing verwendet zwei Tabellen der jeweiligen Größe m. Man weiß, dass die Einfügung einer beliebigen Menge S der Größe n = (1 - delta)m für eine beliebige Konstante delta (0,1) (was einen Lastfaktor n/(2m) von bis zu 1/2 liefert) mit Wahrscheinlichkeit O(1/n) fehlschlägt, falls die Hashfunktionen aus einer Omega(log n)-fach unabhängigen Klasse gewählt werden. Damit läßt sich beweisen, dass die erwarteten amortisierten Kosten einer einzelnen Einfügung konstant sind. Demgegenüber beweisen wir untere Schranken der folgenden Art: Wenn S eine uniform zufällig gewählte Schlüsselmenge der Größe m/2$ ist (Lastfaktor 1/4 (!)), dann schlägt die Einfügung von S mit großer Wahrscheinlichkeit Omega(1), oder sogar 1 - o(1), fehl, falls Funktionen der multiplikativen bzw. der linearen Klasse gewählt werden. Damit beantworten wir eine Frage, die bereits von Pagh und Rodler aufgeworfen wurde, als sie mit Hilfe von Experimenten feststellten, dass es riskant ist, Cuckoo Hashing mit Funktionen der multiplikativen Klasse zu kombinieren. Unsere Resultate zeigen, dass paarweise Unabhängigkeit und uniforme Verteilung der Hashwerte keine Garantie dafür ist, dass Cuckoo Hashing gut funktioniert. Zudem machen unsere Ergebnisse exemplarisch deutlich, dass bei der Anwendung eines kürzlich veröffentlichten Resultates von Mitzenmacher und Vadhan, welches besagt, dass selbst Funktionen aus einfachen, schwach universellen Klassen unter gewissen Bedingungen zu hochgradig unabhängigen und fast uniform zufälligen Werten führen können, Vorsicht geboten ist: Falls dessen Bedingungen nicht erfüllt sind, gilt es unter Umständen nicht.
http://www.db-thueringen.de/servlets/DocumentServlet?id=14080
On risks of using cuckoo hashing with simple universal hash classes. - In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 978-0-89871-680-1, (2009), S. 795-804
Connectivity and diameter in distance graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 17 S., 177 KB). - (Preprint ; M09,12)
http://www.db-thueringen.de/servlets/DocumentServlet?id=12976