English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 querymodel which are linear measurements on the incidence vector induced by theedges; the other is the weaker OR query model which only reveals whether agiven subset of plausible edges is empty or not. At the heart of our study liesa 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 tounderstand the trade-offs between the query complexity and the rounds ofadaptivity needed to solve these problems, for both deterministic andrandomized algorithms. These questions have connections and ramifications tomultiple areas such as sketching, streaming, graph reconstruction, andcompressed sensing. Our main results are:  * For the single element recovery problem, it is easy to obtain adeterministic, $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 isknown to exist.  * We design a deterministic $O(r)$-round, $\tilde{O}(n^{1+1/r})$-OR queryalgorithm for graph connectivity. We complement this with an$\tilde{\Omega}(n^{1 + 1/r})$-lower bound for any $r$-round deterministicalgorithm in the OR-model.  * We design a randomized, $2$-round algorithm for the graph connectivityproblem which makes $\tilde{O}(n)$-OR queries. In contrast, we prove that any$1$-round algorithm (possibly randomized) requires $\tilde{\Omega}(n^2)$-ORqueries.

Graph Connectivity and Single Element Recovery via Linear and OR Queries