Graph Connectivity and Single Element Recovery via Linear and OR Queries
Graph Connectivity and Single Element Recovery via Linear and OR Queries
复制标题
DOI：
10.4230/lipics.esa.2021.7
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Sepehr Assadi;Deeparnab Chakrabarty;S. Khanna
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;Deeparnab Chakrabarty;S. Khanna
本文研究了在两种基本查询模型下，在无向n-顶点多图中寻找生成森林的问题。一种是线性查询模型，它是对由边引起的关联向量的线性测量;另一种是较弱的OR查询模型，它只揭示给定的似然边子集是否为空。我们研究的核心是一个基本问题，我们称之为{\em单个元素恢复}问题：给定一个N维的非负真实的向量x，从支撑中返回一个单个元素x_j > 0。搜索可以在回合中进行，我们的目标是了解查询复杂性和解决这些问题所需的适应性回合之间的权衡，对于确定性算法和随机算法。这些问题与多个领域有联系和分支，例如草图绘制，流，图形重建和压缩传感。我们的主要结果是：* 对于单元素恢复问题，很容易获得一个确定性的$r$轮算法，该算法使每轮$（N^{1/r}-1）$-查询。我们证明这是紧的：任何$r$轮确定性算法必须在某轮中进行$\geq（N^{1/r} - 1）$线性查询。相比之下，已知存在$1$轮$O（\log^2 N）$查询随机化算法，其成功率为99%。* 我们设计了一个确定性的$O（r）$-轮，$\tilde{O}（n^{1+1/r}）$-OR查询算法。我们补充这与$\tilde{\Omega}（n^{1 + 1/r}）$-下界的任何$r$轮确定性算法的OR模型。* 我们设计了一个随机的，2 $轮算法的图连接问题，使$\tilde{O}（n）$-OR查询。相反，我们证明了任何$1$轮算法（可能是随机的）需要$\tilde{\Omega}（n^2）$-OR查询。
We study the problem of finding a spanning forest in an undirected, $n$-vertex multi-graph under two basic query models. One is the Linear query model which are linear measurements on the incidence vector induced by the edges; the other is the weaker OR query model which only reveals whether a given subset of plausible edges is empty or not. At the heart of our study lies a fundamental problem which we call the {\em single element recovery} problem: given a non-negative real vector $x$ in $N$ dimension, return a single element $x_j > 0$ from the support. Queries can be made in rounds, and our goals is to understand the trade-offs between the query complexity and the rounds of adaptivity needed to solve these problems, for both deterministic and randomized algorithms. These questions have connections and ramifications to multiple areas such as sketching, streaming, graph reconstruction, and compressed sensing. Our main results are: * For the single element recovery problem, it is easy to obtain a deterministic, $r$-round algorithm which makes $(N^{1/r}-1)$-queries per-round. We prove that this is tight: any $r$-round deterministic algorithm must make $\geq (N^{1/r} - 1)$ linear queries in some round. In contrast, a $1$-round $O(\log^2 N)$-query randomized algorithm which succeeds 99% of the time is known to exist. * We design a deterministic $O(r)$-round, $\tilde{O}(n^{1+1/r})$-OR query algorithm for graph connectivity. We complement this with an $\tilde{\Omega}(n^{1 + 1/r})$-lower bound for any $r$-round deterministic algorithm in the OR-model. * We design a randomized, $2$-round algorithm for the graph connectivity problem which makes $\tilde{O}(n)$-OR queries. In contrast, we prove that any $1$-round algorithm (possibly randomized) requires $\tilde{\Omega}(n^2)$-OR queries.