BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Sublinear time property testers - Louis-Pascal Xhonneux\, Churchil
 l College
DTSTART:20161019T184000Z
DTEND:20161019T193000Z
UID:TALK67738@talks.cam.ac.uk
CONTACT:Jasper Lee
DESCRIPTION:Property testing is concerned with determining whether an unkn
 own function has a given property. The decision problem in this context is
  relaxed in the following two senses: first\, we are given the promise tha
 t either the property is satisfied or the function is “far” from satis
 fying the property\, and second\, we are allowed to fail with some small e
 rror probability. The slackness introduced allows us to build extremely fa
 st testers\, even ones that run in time sublinear in the size of the input
 . This necessarily requires the algorithm to have sublinear query complexi
 ty\, namely that it only reads in/queries a fraction of the input. We expl
 ore the area of property testers with two illustrative example problems: t
 esting whether a given graph is bipartite and whether a binary input seque
 nce does not contain a fixed string as a subsequence. We conclude with a b
 rief survey on related areas and their connections to property testing.
LOCATION:Wolfson Hall\, Churchill College
END:VEVENT
END:VCALENDAR