New Direct Sum Tests

Alek Westover, Edward Yu, Kai Zheng

A function $f:[n{]}^d\to {\mathbb{F}}_2$ is a \defn{direct sum} if there are functions $L_i:[n]\to {\mathbb{F}}_2$ such that $f(x)={\sum }_i{L}_i(x_i)$. In this work we give multiple…