Computer Science

News and events

10 November 2017

Trading query complexity for sample-based testing and multi-testing scalability

Presented By Dr Oded Lachish, Birkbeck
  • N.1.12, Haslegrave Building

About this event

Abstract: We show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof to a proper testing algorithm.