22 citations · 115 across the 31 of their papers we have counts for
5 papers · 1 filter
New Streaming Algorithms for High Dimensional EMD and MST
Xi Chen, Rajesh Jayaram, Amit Levi +1
We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an -point set , and com…
On the Complexity of Dynamic Submodular Maximization
Xi Chen, Binghui Peng
We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of insertions and deletions. We show that any algorithm that maintains a…
Average-Case Subset Balancing Problems
Xi Chen, Yaonan Jin, Tim Randolph +1
Given a set of input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time $O^*…
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
Xi Chen, Anindya De, Chin Ho Lee +2
In the standard trace reconstruction problem, the goal is to \emph{exactly} reconstruct an unknown source string from independent "traces", which are cop…
Computational Hardness of the Hylland-Zeckhauser Scheme
Thomas Chen, Xi Chen, Binghui Peng +1
We study the complexity of the classic Hylland-Zeckhauser scheme [HZ'79] for one-sided matching markets. We show that the problem of finding an -approximate equilibrium in the H…