arXiv preprint ·
Online matching games in bipartite expanders: applications to bitprobes and dictionaries with non-adaptive probing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A dynamic dictionary also supports the insert and delete operations. The model with cells of bitsize $n + m + 1$ is used, where $n$ and $m$ are the bitsizes of keys and values. We give 2 dictionaries that use $(1+o(1))K$ cells to store $K$ pairs and in which query makes \emph{non-adaptive probes} to the data structure: a static one in which query makes $\smash{\widetilde O(n^2)}$ probes, and a dynamic one in which it makes $\smash{\widetilde O(n^2 \log K)}$ probes. Also, for the first time, a dictionary is given in which all 3 operations are non-adaptive, but the size is larger: $O(nK)$ cells. The constructions are explicit and, consequently, all operations run in time $\poly(n,m)$. 1-bitprobes storage schemes store a set $S \subseteq \{0,1\}^n$ and answer a membership query by reading a single bit. We introduce 1-bitprobes that are {\em dynamic}. Such a scheme is given whose size is smaller than in all previous constructions which are static. The \textsf{query} operation has runtime $n^{O(1)}$. The operations delete and insert have runtime $n^{O(\log n)}$. The proofs rely on a strategy for an online matching game played on a given bipartite graph. An opponent switches left nodes {\em on} and {\em off}. The strategy needs to assign an irrevocable match to a node when it is turned {\em on}. Such games were introduced in the companion paper~\cite{companion-Hall}. The applications in this paper rely on efficient strategies assuming that each node is turned {\em off} after a polynomial number of rounds. We present efficient strategies for (lossless) expanders.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Fast Stencil Computations on a Single Arbitrarily Moving Interval
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.