The Taub Faculty of Computer Science Events and Talks

Property testing studies algorithms that distinguish input in a property P from inputs far from it with only a few queries. There are many natural cases where any property tester for a property P must use a lot of queries, but it is possible to partition P into a few sub-properties P1; P2; :::; Pk, such that distinguishing inputs in Pi from inputs far from P requires only a small amount of queries. This is the case for several well studied properties such as concatenated palindromes, graph isomorphism and string periodicity. We prove that there are some properties for which this is not possible. Towards this end we develop new techniques for proving property testing lower bounds. Our new techniques are based on analyzing a proposed property tester. We show that the queries performed by a tester must, with high probability, query indexes where a uniformly random member of the sub-property has low entropy. We then show how one can aggregate the entropy loss to deduce that a random choice in the sub-property must have low entropy, and therefore the sub-property must be small.