Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

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

Deeparnab Chakrabarty (Dartmouth)

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

Mailing List

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.