Campus Event Calendar
Event Entry
What and Who
New Lower Bounds for the CONGEST model
Seri Khoury
Technion
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 27 July 2017
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We develop a new technique for constructing small-cut graphs that allow us to prove near-linear lower bounds for computing distances, and near-quadratic lower bounds for optimization problems in the CONGEST model. In this talk I will present the technique, and show a near-linear lower bound for computing a (3/2-\epsilon)-approximation for the diameter, and a near-quadratic lower bound for computing minimum vertex cover or maximum independent set.
Based on joint works with Amir Abboud, Keren Censor-Hillel, and Ami Paz.
Contact
Moti Medina
--email hidden
passcode not visible
logged in users only
Moti Medina, 07/25/2017 22:27
Moti Medina, 07/21/2017 10:53 -- Created document.
Moti Medina, 07/21/2017 10:53 -- Created document.