Learning and Testing Variable Partitions

Andrej Bogdanov, Baoxiang Wang

Let $F$ be a multivariate function from a product set ${\Sigma }^n$ to an Abelian group $G$. A $k$-partition of $F$ with cost $\delta$ is a partition of the set of variables $\mathbf{V}$ int…