Seminars & Colloquia Calendar
Graph Connectivity and Single Element Recovery via Linear and OR Measurements: Rounds v Query Trade-offs
Deeparnab Chakrabarty (Dartmouth)
Location: https://theory.cs.rutgers.edu/theory_seminar
Date & time: Wednesday, 14 October 2020 at 11:00AM - 12:00PM
Abstract: Imagine an unknown graph over n known vertices. You have the following “cut-query” oracle: for any subset S of vertices, you can get the number of edges with exactly one endpoint in S. How many queries do you need to find a spanning forest of the graph? How many would you need if you were only allowed only 3 rounds of communication with the oracle?
In this talk, I will discuss the rounds-versus-query complexity trade-off of the above problem. On the way we will meet the following more basic problem which we call single element recovery: given a non-negative, non-zero vector, how many linear measurements are needed to find a single positive coordinate, when only r-rounds of measurements are allowed?
Joint work with Sepehr Assadi and Sanjeev Khanna
