When: Sunday, May 19, 10am
Where: Schreiber 309
Speaker: Yonatan Goldhirsh, Technion
Title: Some properties are not even partially testable
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 P_1,P_2,...,P_k, such that distinguishing inputs in P_i 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.
This is a joint work with Eldar Fischer and Oded Lachish
