BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Testing Graph Properties Very Efficiently
DTSTART:20170616T145000
DTEND:20170616T153500
DTSTAMP:20260407T101211Z
UID:5d72d72136af3276b128c56c2a153df3a2719983d39d7d8b997c47bf
CATEGORIES:Conferences - Seminars
DESCRIPTION:Artur Czumaj\, University of Warwick\nIn this talk\, we will s
 urvey recent advances on the problem of testing graph properties. We will 
 consider a generic problem that for a given input graph G=(V\,E) and a giv
 en graph property P (e.g.\, P may mean bipartiteness\, 3-colorability\, or
  planarity)\, we would like to determine if G satisfies property P or not.
  While the exact problem as defined here is often known to be computationa
 lly very hard (e.g.\, NP-hard\, or even undecidable)\, we will focus on a 
 simpler task\, and we will want to distinguish between the input graphs th
 at satisfy property P from the graphs that are “far away” from satisfy
 ing property P. Being “far away” means that one has to modify the inpu
 t graph in more than\, say\, 1% of its representation to obtain a graph sa
 tisfying property P. We will survey recent results in this area and show t
 hat for many basic properties\, one can test them in this framework very e
 fficiently\, often in sublinear-time\, and sometimes even in constant time
 .
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR