TY - GEN
T1 - Graph connectivity and single element recovery via linear and OR queries
AU - Assadi, Sepehr
AU - Chakrabarty, Deeparnab
AU - Khanna, Sanjeev
N1 - Funding Information: Funding Sepehr Assadi: Supported in part by NSF CAREER award CCF-2047061, and gift from Google Research. Deeparnab Chakrabarty: Supported in part by the NSF awards CCF-1813053 and CCF-2041920. Sanjeev Khanna: Supported in part by the NSF awards CCF-1763514, CCF-1617851, CCF-1934876, and CCF-2008305. Publisher Copyright: © Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna; licensed under Creative Commons License CC-BY 4.0
PY - 2021/9/1
Y1 - 2021/9/1
N2 - We study the problem of finding a spanning forest in an undirected, n-vertex multi-graph under two basic query models. One are Linear queries which are linear measurements on the incidence vector induced by the edges; the other are the weaker OR queries which only reveal 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 single element recovery problem: given a non-negative vector x ∈ RN≥0, the objective is to return a single element xj > 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 as follows: For the single element recovery problem, it is easy to obtain a deterministic, r-round algorithm which makes (N1/r−1)-queries per-round. We prove that this is tight: any r-round deterministic algorithm must make ≥ (N1/r − 1) Linear queries in some round. In contrast, a 1-round O(polylog(N))-query randomized algorithm is known to exist. We design a deterministic O(r)-round, Õ(n1+1/r)-OR query algorithm for graph connectivity. We complement this with an Ω(~ n1+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 Oe(n)-OR queries. In contrast, we prove that any 1-round algorithm (possibly randomized) requires Ω(e n2)-OR queries. A randomized, 1-round algorithm making Oe(n)-Linear queries is already known. All our algorithms, in fact, work with more natural graph query models which are special cases of the above, and have been extensively studied in the literature. These are Cross queries (cut-queries) and BIS (bipartite independent set) queries.
AB - We study the problem of finding a spanning forest in an undirected, n-vertex multi-graph under two basic query models. One are Linear queries which are linear measurements on the incidence vector induced by the edges; the other are the weaker OR queries which only reveal 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 single element recovery problem: given a non-negative vector x ∈ RN≥0, the objective is to return a single element xj > 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 as follows: For the single element recovery problem, it is easy to obtain a deterministic, r-round algorithm which makes (N1/r−1)-queries per-round. We prove that this is tight: any r-round deterministic algorithm must make ≥ (N1/r − 1) Linear queries in some round. In contrast, a 1-round O(polylog(N))-query randomized algorithm is known to exist. We design a deterministic O(r)-round, Õ(n1+1/r)-OR query algorithm for graph connectivity. We complement this with an Ω(~ n1+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 Oe(n)-OR queries. In contrast, we prove that any 1-round algorithm (possibly randomized) requires Ω(e n2)-OR queries. A randomized, 1-round algorithm making Oe(n)-Linear queries is already known. All our algorithms, in fact, work with more natural graph query models which are special cases of the above, and have been extensively studied in the literature. These are Cross queries (cut-queries) and BIS (bipartite independent set) queries.
KW - Duality
KW - Graph connectivity
KW - Group testing
KW - Query models
UR - http://www.scopus.com/inward/record.url?scp=85110847124&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85110847124&partnerID=8YFLogxK
U2 - https://doi.org/10.4230/LIPIcs.ESA.2021.7
DO - https://doi.org/10.4230/LIPIcs.ESA.2021.7
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 29th Annual European Symposium on Algorithms, ESA 2021
A2 - Mutzel, Petra
A2 - Pagh, Rasmus
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th Annual European Symposium on Algorithms, ESA 2021
Y2 - 6 September 2021 through 8 September 2021
ER -