3 papers
cs.DS2025
A Framework for Building Data Structures from Communication Protocols
Alexandr Andoni, Shunhua Jiang, Omri Weinstein
We present a general framework for designing efficient data structures for high-dimensional pattern-matching problems () through communication mode…
cs.DS2025
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai
We present a nearly linear work parallel algorithm for approximating the Held-Karp bound for the Metric TSP problem. Given an edge-weighted undirected graph on edges…
cs.DS2024
Hardness Amplification for Dynamic Binary Search Trees
Shunhua Jiang, Victor Lecomte, Omri Weinstein +1
We prove direct-sum theorems for Wilber's two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the…