Graph Connectivity and Single Element Recovery via Linear and OR Queries

 
 
Deeparnab Chakrabarty
Dartmouth
 
Sublinear Algorithms Workshop,  2022
 
Sanjeev Khanna
Penn
 
Sepehr Assadi
Rutgers
 
Graph Connectivity and Single Element
Recovery via Linear and OR Queries
Single Element Recovery
 
How many queries?
Binary Search
 
> 0
 
= 0
 
Left Half
 
Right Half
 
Recurse on:
 
Works even with an “OR” query
 
Optimal query complexity
Fewer Rounds : Shallow “Binary” Search
 
Round 1
 
Round 2
 
At least one of them > 0
 
Can one do better?
 
Round-v-Query Tradeoff?
Queries on Graphs
Unknown Graph on n-vertices
 
Eg: 
Cut Queries
 
Grebinski, Kucherov ’00
Choi, Kim ‘08
Bshouty, Mazzawi, ’11
Connectivity Question
 
Single Element Recovery: Find an edge incident to a vertex
How many queries are required 
to find a spanning forest of G?
Rounds-v-Query Tradeoff
Deterministic vs Randomized
 
* Failure probability: 1%
 
Jowhari, Salgam, Tardos 2010
 
Ahn, Guha, McGregor 2011
 
Frahling, Indyk, Sohler 2005
 
Focus of this talk: Deterministic Algorithms
 
Perspective
 
Huge literature on 
full
 signal recovery and graph
reconstruction 
using linear and OR measurements
 
Sketching and Dynamic Streaming
 
Cut queries and submodular function minimization
Main Results
Even with linear queries
 
Works even with OR queries
 
Single Element Recovery
 
The general r-round lower bound is an inductive application
of this lower bound idea.
Heart of the matter : Support Trapping
Adversary Setting
N
=
 
Algorithms’ output
 
Adversary Setting
 
N
 
=
 
Algorithms’ output
 
Adversary Setting
 
N
 
=
 
=
Simple Observations
Adversary’s Strategy
Adversary’s Strategy
 
=
 
has a solution.
Invariant
Invariant
Claim:
Support Argument
Claim:
 
Otherwise,
Moving to Inequalities
 
What goes wrong
in the previous argument?
Simple Observations
Farkas Lemma
Open Question 1
Algorithmically, can get logs in denominator
 
Chakrabarti, Stoeckl 2021:
 
True for r=2
 
Open Question 2
 
True for OR queries
 
A “Direct Sum” style question
 
Thanks
!
 
https://arxiv.org/pdf/2007.06098.pdf
Slide Note
Embed
Share

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.


Uploaded on Sep 06, 2024 | 0 Views


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


  1. Graph Connectivity and Single Element Recovery via Linear and OR Queries Sepehr Assadi Rutgers Deeparnab Chakrabarty Dartmouth Sanjeev Khanna Penn Sublinear Algorithms Workshop, 2022

  2. 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?

  3. 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

  4. 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?

  5. 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

  6. 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

  7. 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

  8. 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

  9. 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

  10. 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

  11. 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.

  12. 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 ? ?? = ?

  13. 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 ?? = ?

  14. 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 ?? = ?

  15. 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

  16. 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

  17. 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

  18. 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.

  19. 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

  20. 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

  21. 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:

  22. 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 ?

  23. 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

  24. 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

  25. Farkas Lemma ? ? + ? ? ?? ?,? s.t. ??? ? ? + ? 0 ? ?? Lower bound if and only if a certain ?-dimensional object is non-empty ? ?: ? ? ??

  26. 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

  27. 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

  28. Thanks! https://arxiv.org/pdf/2007.06098.pdf

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#