When: Sunday, April 28, 10am
Where: Schreiber 309
Speaker: Amit Weinstein, Tel Aviv University
Title: Property testing of partially symmetric functions
Given a family of Boolean functions, property testing considers the task of distinguishing between functions of the family and functions that are far from it, by querying the input function at as few locations as possible. Identifying the optimal number of needed queries for each family is the main research goal in this field. A recent modification of this question allows the algorithm to only perform random queries, or choose its queries from a polynomial set of random inputs. These modifications are called passive and active testing, respectively.
In this talk we discuss some recent results in property testing, mostly involving the family of partially symmetric functions, that is, functions which are invariant under reordering of all but a small fraction of their input variables. We provide insight to the query complexity of testing partially symmetric functions in the different testing scenarios, demonstrating a large gap between them. We additionally suggest a strong connection between the family of partially symmetric functions and functions for which isomorphism can be tested efficiently.
The results presented are part of the speaker's PhD thesis on combinatorial aspects of error correction and property testing, which was carried out under the supervision of Prof. Noga Alon. Some of the results are based on joint works with Noga Alon, Eric Blais, Rani Hod and Yuichi Yoshida.