University of Cambridge > > Churchill CompSci Talks > Sublinear time property testers

Sublinear time property testers

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity