Title: Proper subgroup testing

Abstract: Property testing algorithms are designed to extract global properties of the input object by sampling it locally. In this talk we discuss the following problem: Design a proper subgroup tester, namely, one that is given a subgroup H of a group G as input and needs to decide whether H=G or not. To that end, we first translate the problem into a purely combinatorial group theory one, which can be shown to be a non-commutative counterpart of error correcting codes. We then use the standard theory of error correcting codes as inspiration, and provide several solutions to this problem with various parameters.

This talk is based on a joint work with Irit Dinur and Alex Lubotzky.