Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Deeparnab Chakrabarty, Dartmouth College

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.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.