11 citations · 38 across the 20 of their papers we have counts for
6 papers · 1 filter
A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions
Yuzhou Gu, Xin Li, Yinzhan Xu
We study the query complexity of Boolean functions in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In th…
Submodular Maximization under the Intersection of Matroid and Knapsack Constraints
Yu-Ran Gu, Chao Bian, Chao Qian
Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations resea…
Fast Sampling of -Matchings and -Edge Covers
Zongchen Chen, Yuzhou Gu
For an integer , a -matching (resp. -edge cover) of a graph is a subset of edges such that every vertex is incident with at most (resp. at l…
Optimal Bounds for Noisy Sorting
Yuzhou Gu, Yinzhan Xu
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that comparisons are both necessary and sufficient to sort…
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams +1
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in time, and it is widely open whether it has an time algori…
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
Lijie Chen, Erik D. Demaine, Yuzhou Gu +3
Since the introduction of retroactive data structures at SODA 2004, a major unsolved problem has been to bound the gap between the best partially retroactive data structure (where…