14 documents found

Dissertation
All rights reserved
2020-11-27

Random hypergraphs for hashing-based data structures

This thesis concerns dictionaries and related data structures that rely on providing several random possibilities for storing each key. Imagine information on a set S of m = |S| keys should be stored in n memory locations, indexed by [n] = {1,…,n}. Each object x [ELEMENT OF] S is assigned a small set...
Article / Chapter
CC BY 3.0
2019-09

Efficient Gauss elimination for near-quadratic matrices with one short...

Saarbrücken/Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2019-09
Article / Chapter
CC BY 3.0
2019-09

Dense peelable random uniform hypergraphs

Saarbrücken/Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2019-09
Article / Chapter
CC BY 3.0
2019-03

Constant-time retrieval with O(log m) extra bits

Saarbrücken/Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2019-03
Article / Chapter
CC BY 3.0
2018-08

A subquadratic algorithm for 3XOR

Saarbrücken/Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2018-08
Book chapter
CC BY 3.0
2017-12-19

Cuckoo hashing with overlapping buckets

Wadern: Schloss Dagstuhl, 2017-12-19
Proceedings
CC BY 3.0
2017-12-19

Theory and applications of hashing : report from Dagstuhl Seminar 17181

This report documents the program and the topics discussed of the 4-day Dagstuhl Seminar 17181 “Theory and Applications of Hashing”, which took place May 1–5, 2017. Four long and eighteen short talks covered a wide and diverse range of topics within the theme of the workshop. The program left sufficient...
Wadern: Schloss Dagstuhl, 2017-12-19
Dissertation
2016-02-17

On Statistical Data Compression

Im Zuge der stetigen Weiterentwicklung moderner Technik wächst die Menge an zu verarbeitenden Daten.Es gilt diese Daten zu verwalten, zu übertragen und zu speichern.Dafür ist Datenkompression unerlässlich.Gemessen an empirischen Kompressionsraten zählen Statistische Datenkompressionsalgorithmen...
Dissertation
2015-11-18

Algorithms for computing the 2-vertex-connected components and the 2-blocks...

In dieser Dissertation beschäftigen wir uns mit mehreren Problemen in gerichteten Graphen. Zuerst betrachten wir das Problem der Berechnung der $2$-fach knotenzusammenhängenden Komponenten in gerichteten Graphen. Wir präsentieren einen neuen Algorithmus zur Lösung dieses Problems in Zeit $O(nm)$...
Dissertation
2015-05-06

Thresholds for Matchings in Random Bipartite Graphs with Applications to...

Wir betrachten randomisierte Algorithmen, die bei Eingabe einer Menge S von n Schlüsseln aus einem Universum U,oder einer Menge von n Schlüssel-Wert-Paaren eine Datenstruktur für eine der folgenden Aufgaben bauen.Bei Aufruf der Operation lookup für einen Schlüssel x aus U: * Entscheide, ob x Element...
Book chapter
CC BY-NC-ND 3.0
2012-02

On randomness in Hash functions

In the talk, we shall discuss quality measures for hash functions used in data structures and algorithms, and survey positive and negative results. (This talk is not about cryptographic hash functions.) For the analysis of algorithms involving hash functions, it is often convenient to assume the hash...
Saarbrücken/Wadern: Schloss Dagstuhl - Leibniz-Center for Informatics, 2012-02
Dissertation
2009-12-10

Contributions to Structural Communication Complexity

In der Dissertation werden strukturelle Probleme in YaosKommunikationsmodell untersucht, die sich thematisch dreiBereichen dieses Gebietes zuordnen lassen:Der erste Teil der Arbeit beschäftigt sich mit dem fundamentalenProblem der Herleitung unterer Schranken für die randomisierteKommunikationskomplexität....
Dissertation
2009-10-05

On Risks of Using a High Performance Hashing Scheme with Common Universal...

The contribution of this thesis is a mathematical analysis a high performance hashing scheme called cuckoo hashing when combined with two very simple and efficient classes of functions that we refer to as the multiplicative class and the linear class, respectively. We prove that cuckoo hashing tends...
Article / Chapter
2008-12-18

Tight bounds for blind search on the integers

We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq...