4 papers · 1 filter
Almost Optimal Multiple Source Shortest Paths and Reachability
Barna Saha, Yinzhan Xu, Christopher Ye
Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweig…
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…
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black, Arya Mazumdar, Barna Saha +1
The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components,…
Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
Yuzhou Gu, Xin Li, Yinzhan Xu
In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability . In this paper, we obta…