# Combinatorics Seminar

When: Sunday, April 28, 10am

Where: Schreiber 309

Speaker: Amit Weinstein, Tel Aviv University

Title: Property testing of partially symmetric functions

## Abstract:

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.

redesigned by barak soreq