Zobrazeno 1 - 10
of 61
pro vyhledávání: '"Yu, Huacheng"'
Dictionaries have been one of the central questions in data structures. A dictionary data structure maintains a set of key-value pairs under insertions and deletions such that given a query key, the data structure efficiently returns its value. The s
Externí odkaz:
http://arxiv.org/abs/2310.20536
Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work "succincter" by Patrascu showed that any aB-tree can be stored using only two bits of redundancy, while supporting queries to the tree in time proportional to its dep
Externí odkaz:
http://arxiv.org/abs/2309.12950
Autor:
Yu, Huacheng, Zhan, Wei
We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of $n$ elements in $[n]$, outputs $O(n)$ elements, such that: (
Externí odkaz:
http://arxiv.org/abs/2306.15817
A dictionary data structure maintains a set of at most $n$ keys from the universe $[U]$ under key insertions and deletions, such that given a query $x \in [U]$, it returns if $x$ is in the set. Some variants also store values associated to the keys s
Externí odkaz:
http://arxiv.org/abs/2306.02253
Autor:
Larsen, Kasper Green, Yu, Huacheng
In this work, we prove a $\tilde{\Omega}(\lg^{3/2} n )$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions.
Externí odkaz:
http://arxiv.org/abs/2304.08745
Network administrators want to detect TCP-level packet reordering to diagnose performance problems and attacks. However, reordering is expensive to measure, because each packet must be processed relative to the TCP sequence number of its predecessor
Externí odkaz:
http://arxiv.org/abs/2301.00058
Naively storing a counter up to value $n$ would require $\Omega(\log n)$ bits of memory. Nelson and Yu [NY22], following work of [Morris78], showed that if the query answers need only be $(1+\epsilon)$-approximate with probability at least $1 - \delt
Externí odkaz:
http://arxiv.org/abs/2211.03917
Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algori
Externí odkaz:
http://arxiv.org/abs/2209.14775
Autor:
Yu, Huacheng
In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\{0,1\}$, the $n$-fold XOR function $f^{\oplus n}:\mathcal{X}^n\times \mathcal{Y}^n\rightarrow
Externí odkaz:
http://arxiv.org/abs/2208.11152
For a directed graph $G$ with $n$ vertices and a start vertex $u_{\sf start}$, we wish to (approximately) sample an $L$-step random walk over $G$ starting from $u_{\sf start}$ with minimum space using an algorithm that only makes few passes over the
Externí odkaz:
http://arxiv.org/abs/2102.11251