Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:New Lower Bounds for the CONGEST model
Speaker:Seri Khoury
coming from:Technion
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 27 July 2017
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
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
Name(s):Moti Medina
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
Moti Medina, 07/21/2017 10:53 AM
Last modified:
halma/MPII/DE, 10/17/2018 04:13 PM
  • Moti Medina, 07/25/2017 10:27 PM
  • Moti Medina, 07/21/2017 10:53 AM -- Created document.