Graph Connectivity and Single Element Recovery via Linear and OR Measurements: Rounds v Query Trade-offs

Start Date: October 14, 2020
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Organizers: Sepehr Assadi || Swastik Kopparty
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Deeparnab Chakrabarty - Dartmouth College
Event Location: Online Event
Event Additional Info: <p>The <strong>Theory of Computing Seminar is being held online. </strong>Contact the organizers for the link to the seminar.</p>
Presentation Type: Stand Alone Presentation
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.

Events