Testing Linear-Invariant Non-Linear Properties

Arnab Bhattacharyya, Victor Chen, Madhu Sudan +1

We consider the task of testing properties of Boolean functions that are invariant under linear transformations of the Boolean cube. Previous work in property testing, including th…