论文标题
通过线性和 / /查询的图形连接和单个元素恢复
Graph Connectivity and Single Element Recovery via Linear and OR Queries
论文作者
论文摘要
我们研究了在两个基本查询模型下找到一个无向的，$ n $ vertex的多画的问题的问题。一种是线性查询模型，是在边缘引起的入射矢量上的线性测量值。另一个是较弱或查询模型，它仅揭示给定的合理边缘是否为空的子集。我们研究的核心是一个基本问题，我们称之为{\ em单元素恢复}问题：给定$ n $ dimension In $ n $ dimension中的非负实际矢量$ x $，从支持中返回单个元素$ x_j> 0 $。查询可以在回合中进行，我们的目标是了解查询复杂性与解决这些问题所需的适应性回合之间的权衡，以确定性和随机算法。这些问题与多个领域（例如素描，流式，图形重建和压缩感测）具有连接和分歧。我们的主要结果是： *对于单个元素恢复问题，很容易获得确定性的，$ r $ round算法，该算法使$（n^{1/r} -1）$ - 每轮查询。我们证明这很紧张：任何$ r $ round的确定性算法都必须使$ \ geq（n^{1/r} -1）$在某个回合中$线性查询。相比之下，已知存在99％的时间的$ 1 $ round $ o（\ log^2 n）$ - 查询随机算法。 *我们设计了确定性的$ o（r）$ - 圆形，$ \ tilde {o}（n^{1+1/r}）$ - 或查询图形连接的算法。我们用$ \tildeΩ（n^{1 + 1/r}）$ - 对于OR模型中的任何$ r $ rund-Round确定算法的下限。 *我们为图形连接问题设计了一个随机的，$ 2 $的算法，该算法使$ \ tilde {o}（n）$或查询。相比之下，我们证明任何$ 1 $ - 环算法（可能是随机的）都需要$ \tildeΩ（n^2）$或查询。
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Ω(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Ω(n^2)$-OR queries.
