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
Chiara Damiolini, Ian Coley and Franco Rota -Charles Weibel Organizer's Page
Narek Hovsepyan and Ewerton Rocha Vieira Organizer's page
Ziming Shi, Sagun Chanillo, Xiaojun Huang, Chi Li, Jian Song Seminar website Old seminar website
Sepehr Assadi Seminar webpage
Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage
Robert Dougherty-Bliss and Doron Zeilberger --> homepage
Paul Feehan, Daniel Ketover, Natasa Sesum Organizer's webpage
Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage
Hong Chen Seminar webpage
Fanxin Wu and Nkhalo Malawo Organizer's website
James Holland; Organizer website
Organizers: Maxime Van de Moortel and Avy Soffer. Organizer's Page
Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum Organizer's Webpage
Organizer: Luochen Zhao
Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song Organizer's Page
Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage
Simon Thomas website
Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page
Joel Lebowitz, Michael Kiessling
Yanyan Li, Dennis Kriventsov Organizer's Webpage
Alex V. Kontorovich, Vlada Sedláček seminar website
Stephen D. Miller
Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum
Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page
Fioralba Cakoni Seminar webpage
- Show events from all categories
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.
