## Abstract

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 ∈ R^{N}_{≥}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 (N^{1/r}−1)-queries per-round. We prove that this is tight: any r-round deterministic algorithm must make ≥ (N^{1/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, Õ(n^{1+1/r})-OR query algorithm for graph connectivity. We complement this with an Ω(~ 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 O^{e}(n)-OR queries. In contrast, we prove that any 1-round algorithm (possibly randomized) requires Ω(^{e} n^{2})-OR queries. A randomized, 1-round algorithm making O^{e}(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.

Original language | English (US) |
---|---|

Title of host publication | 29th Annual European Symposium on Algorithms, ESA 2021 |

Editors | Petra Mutzel, Rasmus Pagh, Grzegorz Herman |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772044 |

DOIs | |

State | Published - Sep 1 2021 |

Event | 29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal Duration: Sep 6 2021 → Sep 8 2021 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 204 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 29th Annual European Symposium on Algorithms, ESA 2021 |
---|---|

Country/Territory | Portugal |

City | Vitual, Lisbon |

Period | 9/6/21 → 9/8/21 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Duality
- Graph connectivity
- Group testing
- Query models