activity
20162026
most citedComputing and Testing Small Vertex Connectivity in Near-Linear Time and Queries

6 citations · 20 across the 19 of their papers we have counts for

collaborators
Showing 2024 · cs.DSShow all

2 papers · 2 filters

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…

cs.DS2024

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…