Graph Connectivity and Single Element Recovery via Linear and OR Queries

Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna

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…