# Combinatorics Seminar

When: Sunday, May 19, 10am

Where: Schreiber 309

Speaker: Yonatan Goldhirsh, Technion

Title: Some properties are not even partially testable

## Abstract:

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

redesigned by barak soreq