6 papers
A Sharp Analysis of Fixed Offset Hash Tables
Yuhao Guo, Seth Pettie, Chengzhang Wan
We consider the class of open addressing hash tables that uses a fixed offset sequence to find an open slot in the table. As special cases this subsumes li…
Iterative Randomized Rounding for Better-Than-2 k-Median Approximation
Jarosław Byrka, Yuhao Guo, Yang Hu +5
We study the classic -median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsil…
A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes
Yuhao Guo, Seth Pettie, Chengzhang Wan
In open addressed hashing, quadratic probing is attractive for striking a nice balance between having a high locality of reference and a low number of probes per search. However, t…
The Greedy Binary Search Tree is Non-trivially Competitive
Yuhao Guo, Seth Pettie, Daniel Skora +1
We prove that the binary search tree is -competitive. It is widely conjectured that is -competitive, but before…
-Clustering via Iterative Randomized Rounding
Jarosław Byrka, Yuhao Guo, Yang Hu +3
In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for -clustering. As a starting point, we obtain an iterative round…
Electrically functionalized body surface for deep-tissue bioelectrical recording
Dehui Zhang, Yucheng Zhang, Dong Xu +14
Directly probing deep tissue activities from body surfaces offers a noninvasive approach to monitoring essential physiological processes1-3. However, this method is technically cha…