Graph Connectivity and Single Element Recovery via Linear and OR Queries
The content discusses the concepts of graph connectivity and single element recovery using linear and OR queries. It delves into the strategies, algorithms, and tradeoffs involved in determining unknown vectors, edges incident to vertices, and spanning forests in graphs. The talk contrasts deterministic and randomized algorithms, exploring the potential of randomization in reducing query complexity. Various techniques such as compressed sensing, sparse recovery, and adaptivity are highlighted for efficient signal recovery and graph reconstruction.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Graph Connectivity and Single Element Recovery via Linear and OR Queries Sepehr Assadi Rutgers Deeparnab Chakrabarty Dartmouth Sanjeev Khanna Penn Sublinear Algorithms Workshop, 2022
Single Element Recovery ? is an unknown non-zero vector ? 0 Measurement: For any subset ? ? , can get ? ? ?? Goal: Find a coordinate ? with ??> 0 How many queries?
Binary Search ?/2 > 0 = 0 log2? queries Recurse on: Right Half Left Half Works even with an OR query Optimal query complexity Adaptive Algorithm: log2? rounds
Fewer Rounds : Shallow Binary Search ? Round 1 ? queries At least one of them > 0 ? queries Round 2 In ? rounds, ?1/? queries per round suffices Can one do better? Round-v-Query Tradeoff?
Queries on Graphs Linear Measurement ? 2 Input: ? 0 Output: ? ? Eg: Cut Queries Grebinski, Kucherov 00 Choi, Kim 08 Bshouty, Mazzawi, 11 Unknown Graph on n-vertices ? 2 Think of as unknown vector ? 0
Connectivity Question [?,?,?,?,?,?] How many queries are required to find a spanning forest of G? Rounds-v-Query Tradeoff Single Element Recovery: Find an edge incident to a vertex
Deterministic vs Randomized * Failure probability: 1% With randomization*, single element recovery can be solved in one round using ?(log2?) queries via 0-samplers Jowhari, Salgam, Tardos 2010 Frahling, Indyk, Sohler 2005 With randomization*, a spanning forest can be constructed in one round using ?(?log3?) linear queries Ahn, Guha, McGregor 2011 Focus of this talk: Deterministic Algorithms
Perspective Huge literature on full signal recovery and graph reconstruction using linear and OR measurements - Compressed Sensing/Group Testing - Sparse Recovery: ?(? polylog ?) queries in one round - Reconstruction: ?(? polylog N) queries in one round for m-edge graphs - Adaptivity helps the log factors Sketching and Dynamic Streaming Cut queries and submodular function minimization
Main Results Any r-round deterministic algorithm for single element recovery must make (?1/? 1) queries in some round Even with linear queries There is an ?(?) round, ?(?1+1 deterministically finding a spanning forest in an unknown multigraph. ?) query algorithm for Works even with OR queries
Single Element Recovery ? is an unknown non-zero vector ? 0 Measurement: For any subset ? ? , can get ? ? ?? Goal: Find a coordinate ? with ??> 0 Any r-round deterministic algorithm for single element recovery must make (?1/? 1) queries in some round
Heart of the matter : Support Trapping Consider algorithms that make one round of ? linear queries, and return a set ? [?] of size ? such that ? ? 0 Need to show that both? and ?can t be ? Otherwise, there will be a ? query 2-round algorithm The general r-round lower bound is an inductive application of this lower bound idea.
Adversary Setting N ? ? ? = Algorithms output ? Given any ? ? matrix ?, we need to produce answer vector ? s.t. for any subset S of size ?, there is some consistent ? 0 with ? ?= 0 ? ?? = ?
Adversary Setting N ? ? ? = Algorithms output ? Given any ? ? matrix ?, we need to produce answer vector ? s.t. for any subset S of size ?, there is some consistent ? 0 with ?? ? ? = 0 ?? = ?
Adversary Setting N ensures ? is non-zero 1 1 1 1 1 = ? ? ? ? s.t. for any subset S of size ?, there is some consistent ? 0 with ?? ? Given any ? ? matrix ?, we need to produce answer vector ? ? = 0 ? ? = 1 ?? = ?
Simpler case: ? can be -ve Given any ? ? matrix ?, we need to produce answer vector ? s.t. for any subset S of size ?, there is some ? ? with ? ? = 1 ?? = ? ?? ? = 0
Simple Observations If ?contains a row with ? non-zero entries, the corresponding answer in ? should be 0. If some row of ?is in the span of ?and the other rows of ?, then it can be removed. A set ?with ?? not in the span of queries, is safe ? ? = 1 ?? = ? ?? Can find an ? such that for any ? ? = 0
Adversarys Strategy Try to get to a collection ? of (q+1) rows s.t ? ? All original queries are in span ? ? ?, ? ?: either ?? span ? or, ?? span ?small where ?small are the rows of ? with ? non-zero elts
Adversarys Strategy 1 1 1 1 1 ? + 1 0 ? ?small = ?big ? ? All original queries are in span ? ? from ? ? ? = 1 ? ?, ? ?: either ?? span ? ?? = ? ?? or, ?? span ?small ? = 0 has a solution.
Finding such a ? Try to get to a collection ? of (q+1) rows s.t ? ? All original queries are in span ? ? ?, ? ?: either ?? span ? where ?small are the rows of ? with ? non-zero elts
Finding such a ? 1 1 1 1 ? + 1 ?small ?big Invariant ? ? All original queries are in span ? Let ? ? , with ? ?, such that ?? span ?but span ?small
Finding such a ? 1 1 1 1 ? + 1 ?small ?big Invariant ? ? ? + ?? ? ? All original queries are in span ? Can t occur > ? times Let ? ? , with ? ?, such that ?? span ?but span ?small Some ? ?bigmust be involved in expressing ?? Claim:
Support Argument Let ? ? , with ? ?, such that ?? span ?but span ?small Some ? ?bigmust be involved in expressing ?? Claim: ??= ? + lin. comb. of ? small vectors Otherwise, ? = lin. comb. of (? + 1) small vectors ? ? + 1 ? contradicting both ? and ? being ?
Moving to Inequalities Given any ? ? matrix ?, we need to produce answer vector ? s.t. for any subset S of size ?, there is some ? 0 ? with ? ? = 1 ?? = ? ?? ? 0 What goes wrong in the previous argument? ? = 0
Simple Observations If ?contains a row with ? non-zero entries, the corresponding answer in ? should be 0. If some row of ?is in the span of ?and the other rows of ?, then it can be removed. A set ?with ?? not in the span of queries, is safe ? ? = 1 ?? = ? ?? for any? ? = 0 Not true with ? 0
Farkas Lemma ? ? + ? ? ?? ?,? s.t. ??? ? ? + ? 0 ? ?? Lower bound if and only if a certain ?-dimensional object is non-empty ? ?: ? ? ??
Open Question 1 The lower bounds hold only for real-valued vectors. Can one prove (?1/?) lower bound for r-rounds, when the unknown vector ? {0,1}?? Algorithmically, can get logs in denominator Chakrabarti, Stoeckl 2021: True if the computation is done on the ring ?kfor some constant k True for r=2
Open Question 2 Can one prove ?1+1 forest using linear queries in r-rounds? ? lower bound for finding spanning A Direct Sum style question True for OR queries
Thanks! https://arxiv.org/pdf/2007.06098.pdf
