Sublinear time property testers

Add to your list(s) Download to your calendar using vCal

• Louis-Pascal Xhonneux, Churchill College
• Wednesday 19 October 2016, 19:40-20:30
• Wolfson Hall, Churchill College.

If you have a question about this talk, please contact Jasper Lee.

Property testing is concerned with determining whether an unknown function has a given property. The decision problem in this context is relaxed in the following two senses: first, we are given the promise that either the property is satisfied or the function is “far” from satisfying the property, and second, we are allowed to fail with some small error probability. The slackness introduced allows us to build extremely fast testers, even ones that run in time sublinear in the size of the input. This necessarily requires the algorithm to have sublinear query complexity, namely that it only reads in/queries a fraction of the input. We explore the area of property testers with two illustrative example problems: testing whether a given graph is bipartite and whether a binary input sequence does not contain a fixed string as a subsequence. We conclude with a brief survey on related areas and their connections to property testing.

This talk is part of the Churchill CompSci Talks series.

This talk is included in these lists:

• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Churchill CompSci Talks
• Interested Talks
• Trust & Technology Initiative - interesting events
• Wolfson Hall, Churchill College
• bld31
• computer science
• ndk22's list
• ob366-ai4er
• rp587
• se393's list

Note that ex-directory lists are not shown.